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 larges开发者_JAVA技巧t 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.

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.

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

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();
}

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).

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);

}

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;
   }
   

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)

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;
}

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)