Find the subsequence with largest sum of elements in an array

Question

Hi,

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

Just add all positive numbers.

Answer 5

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