Subsequence with maximum sum in array of ints

Question

Given an array of integers, how can you find two indices, i and j, such that the sum of the elements in the indices is maximized, in linear time?

Answer 1

Simple. Assume you're given the array a. First, you calculate the array s, where s[i] = a[0]+a[1]+...+a[i]. You can do it in linear time:

s[0]=a[0];
for (i=1;i<N;i++) s[i]=s[i-1]+a[i];

Now, the sum a[i]+a[i+1]+..+a[j] is equal to s[j]-s[i-1]. For a fixed j, to maximize the value of this difference, you should find a minimal s[i-1] in range of 0..(j-1).

Imagine a usual algorithm to find minimal value in the array.

min = x[j];
for (j=1; j<N; j++)
  if (x[j] < min)
    min = x[j];

You iterate and compare each array element to min... But on each iteration this min is the lowest value in array, where index range is of 0..j! And that's what we're looking for!

global_max = s[1]-s[0];
local_min = s[0];
for (j=1; j<N; j++){
  // here local_min is the lowest value of s[i], where 0<=i<j
  if (s[j] - s[local_min]  > global_max) {
     global_max = s[j] - s[local_min]
     //update indices
     max_i = local_min_index;
     max_j = j;
  }
  //update local_min for next iteration
  if (s[j]<local_min){
    local_min = s[j];
    // update indices
    local_min_index = j;
  }
}

Answer 2

from my copy of programming pearls:

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)