CODEWITHSUNDEEP
c++calgorithm
brett
brett

Reputation: 5649

Find the subsequence with largest sum of elements in an array

I recently interviewed with a company and they asked me to write an algorithm that finds the subsequence with largest sum of elements in an array. The elements in the array can be negative. Is there a O(n) solution for it? Any good solutions are very much appreciated.

Upvotes: 14

Views: 44967

Answers (9)

Akshat Divya
Akshat Divya

Reputation: 86

Since, we need to find the Maximum Sub-sequence Sum, We can:

  1. Sort the Array In descending order.
  2. Take two variable sum and maxSum.
  3. Run a for loop till length n.
  4. Update maxSum when sum > maxSum.

The Java Code Snippet will be something line this:

Arrays.sort(a, Collections.reverseOrder());
int sum = 0;
for (int i = 0; i < a.length; i++) {
 sum = sum + a[i];
     if (sum > maxSum) 
         maxSum = sum;
}
System.out.println(maxSum);

Time Complexity: O(nlogn)

Upvotes: 0

whizvids
whizvids

Reputation: 248

If you are asking what is a contiguous subsequence for which the sum is maximum, I have found 4 algos so far:-

  1. Brute-force: Find all possible sums using nested loops and keep updating the maxSum if you find a sum greater than previous set value of maxSum. The time complexity is O(n^2)

  2. Dynamic Programming Solution: This is a remarkably elegant solution which I found on StackOverflow itself - https://stackoverflow.com/a/8649869/2461567v - Time complexity : O(n), Space complexity : O(n)

  3. DP without memory - Kadane Algorithm -https://en.wikipedia.org/wiki/Maximum_subarray_problem - Time complexity : O(n), Space complexity : O(1)

  4. Divide and Conquer Solution - http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf Time complexity : O(nlgn)

Upvotes: -1

vran freelancer
vran freelancer

Reputation: 17

This problem can be solved two different ways.

The first approach is have two variables called sum and MaxSum.

  1. We will keep on adding values to the sum and will compare with the MaxSum, if the value for the sum is greater than the MaxSum - will assign sum value to the MaxSum

  2. If during the process the value for the sum goes below 0, we will reset the sum and will start adding new number from the next index on-wards. The sample code for the above solution is provided as below:

    private static void FindMaxSum(int[] array)
{
    int sum = 0;
    int MaxSum = 0;

    for (int i = 0; i < array.Length; i++)
    {
        sum += array[i];

        if (sum > MaxSum)
        {
            MaxSum = sum;
        }
        else if (sum < 0)
        {
            sum = 0;
        }
    }
    Console.WriteLine("Maximum sum is: " + MaxSum);
}

The second approach to solve this problem is that we will go through each and every element in an array. We will have same 2 variables of sum and MaxSum.

  1. First we will compare the addition of sum with the next array element and the sum itself. Who ever is greater - that value will be stored in the sum variable.

  2. Next we will compare the values of sum and MaxSum and whoever has greater value - we will save that value in the MaxSum variable. The sample code is as mentioned below: 

    private static void FindMaxSum(int[] array)
{
    int sum = array[0], Maxsum = array[0];

    for (int i = 1; i < array.Length; i++)
    {
        sum = Max(sum + array[i], array[i]);
        Maxsum = Max(sum, Maxsum);               
    }

    Console.WriteLine("Maximum sum is: " + Maxsum);
}

private static int Max(int a, int b)
{
    return a > b ? a : b;
}

Upvotes: 0

asim kadav
asim kadav

Reputation: 23

void longsub(int a[], int len)  {

        int localsum = INT_MIN;
        int globalsum = INT_MIN;
        int startindex = 0,i=0;
        int stopindex = 0;
        int localstart = 0;

        for (i=0; i < len; i++) {
                if (localsum + a[i] < a[i]) {
                        localsum = a[i];
                        localstart = i;
                }
                else {
                        localsum += a[i];
                }

                if (localsum > globalsum) {
                        startindex = localstart;
                        globalsum =  localsum;
                        stopindex = i;
                }

        }

        printf ("The begin and end indices are %d -> %d (%d).\n",startindex, stopindex, globalsum);

}

Upvotes: 1

Shobhit
Shobhit

Reputation: 49

Try the following code:

#include <stdio.h>

int main(void) {
    int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3};
    int cur = arr[0] >= 0? arr[0] : 0, max = arr[0];
    int start = 0, end = 0;
    int i,j = cur == 0 ? 1 : 0;
    printf("Cur\tMax\tStart\tEnd\n");
    printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
    for (i = 1; i < 10; i++) {
        cur += arr[i];
        if (cur > max) {
            max = cur;
            end = i;
            if (j > start) start = j;
        }     
        if (cur < 0) {
            cur = 0;
            j = i+1;
        }
        printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
    }
    getchar();
}

Upvotes: 4

snowgoose
snowgoose

Reputation: 1

C function looks like this:

int largest(int arr[], int length)
{
  int sum= arr[0];
  int tempsum=0;
  for(int i=0;i<length;i++){
     tempsum+=arr[i];
     if(tempsum>sum)
        sum=tempsum;
     if(tempsum<0)
        tempsum=0;
  }
  return sum;
}

Upvotes: -1

Matthew
Matthew

Reputation: 48304

If you want the largest sum of sequential numbers then something like this might work:

$cur = $max = 0;
foreach ($seq as $n)
{
  $cur += $n;
  if ($cur < 0) $cur = 0;
  if ($cur > $max) $max = $cur;
}

That's just off the top of my head, but it seems right. (Ignoring that it assumes 0 is the answer for empty and all negative sets.)

Edit:

If you also want the sequence position:

$cur = $max = 0;
$cur_i = $max_i = 0; 
$max_j = 1;

foreach ($seq as $i => $n)
{
  $cur += $n;
  if ($cur > $max)
  {
    $max = $cur;
    if ($cur_i != $max_i)
    {
      $max_i = $cur_i;
      $max_j = $max_i + 1;
    }
    else
    {
      $max_j = $i + 1;
    }
  }

  if ($cur < 0)
  {
    $cur = 0;
    $cur_i = $i + 1;
  }
}

var_dump(array_slice($seq, $max_i, $max_j - $max_i), $max);

There might be a more concise way to do it. Again, it has the same assumptions (at least one positive integer). Also, it only finds the first biggest sequence.

Edit: changed it to use max_j (exclusive) instead of max_len.

Upvotes: 16

Eyal Schneider
Eyal Schneider

Reputation: 22456

If you mean longest increasing subsequence, see codaddict's answer.

If on the other hand you mean finding the sub array with maximum sum (makes sense only with negative values), then there is an elegant, dynamic programming style linear time solution:

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Upvotes: 14

codaddict
codaddict

Reputation: 455380

I assume you mean longest increasing subsequence.

There is no O(n) solution for that.

A very naive solution would be to create a duplicate array, sort it in O(NlogN) and then find the LCS of the sorted array and original array which takes O(N^2).

There also is a direct DP based solution similar to LCS which also takes O(N^2), which you can see here.

But if you meant longest increasing sequence (consecutive). This can be done in O(N).

Upvotes: 3

Related Questions