Subsequence with maximum sum in array of ints [duplicate]

Question

Given an array of integers, how can you find two indices, i and j, such that the sum of the elements in the subarray starting and ending at 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[0];
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 = a[0];
max_i = max_j = 0;
local_min_index = 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_index] > global_max) {
     global_max = s[j] - s[local_min_index]
     //update indices
     max_i = local_min_index + 1;
     max_j = j;
  }
  //update local_min_index 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)

Answer 3

this python code returns the bounds of the sequence. in terms of the original question, i=bestlo, j=besthi-1.

#
# given a sequence X of signed integers,
# find a contiguous subsequence that has maximal sum.
# return the lo and hi indices that bound the subsequence.
# the subsequence is X[lo:hi] (exclusive of hi).
#
def max_subseq(X):
    #
    # initialize vars to establish invariants.
    # 1: best subseq so far is [bestlo..besthi), and bestsum is its sum
    # 2: cur subseq is [curlo..curhi), and cursum is its sum
    #
    bestlo,besthi,bestsum  =  0,0,0
    curlo,curhi,cursum  =  0,0,0
    for i in xrange(len(X)):
        # extend current subseq and update vars
        curhi = i+1
        cursum += X[i]
        if cursum <= 0:
            #
            # the current subseq went under water,
            # so it can't be usefully extended.
            # start fresh at next index.
            #
            curlo = curhi
            cursum = 0
        elif cursum > bestsum:
            # adopt current subseq as the new best
            bestlo,besthi,bestsum  =  curlo,curhi,cursum

    return (bestlo,besthi)

and here are some doctest examples that this code passes.

    r'''
    doctest examples:
    >>> print max_subseq([])
    (0, 0)
    >>> print max_subseq([10])
    (0, 1)
    >>> print max_subseq([-1])
    (0, 0)
    >>> print max_subseq(xrange(5))
    (1, 5)
    >>> print max_subseq([-1, 1, -1])
    (1, 2)
    >>> print max_subseq([-1, -1, 1, 1, -1, -1, 1, 2, -1])
    (6, 8)
    >>> print max_subseq([-2, 11, -4, 13, -5, -2])
    (1, 4)
    >>> print max_subseq([4, -3, 5, -2, -1, 2, 6,-4])
    (0, 7)
    '''

Answer 4

You actually need Kadane's algorithm modification that remembers lower and upper bounds for the sub-array, here's C++11 code:

#include <iostream>
#include <vector>

typedef std::pair<std::vector<int>::iterator, std::vector<int>::iterator> SubSeq;

SubSeq getMaxSubSeq(std::vector<int> &arr) {
    SubSeq maxSequence{arr.begin(), arr.begin()};
    auto tmpBegin = arr.begin();
    int maxEndingHere = 0;
    int maxSoFar = 0;

    for(auto it = arr.begin(); it < arr.end(); ++it) {
        int currentSum = maxEndingHere + *it;

        if(currentSum > 0) {
            if(maxEndingHere == 0) {
                tmpBegin = it;
            }
            maxEndingHere = currentSum;
        } else {
            maxEndingHere = 0;
        }

        if(maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere;
            maxSequence.first = tmpBegin;
            maxSequence.second = it + 1;
        }
    }

    return maxSequence;
}

int main()
{
    std::vector<int> arr{-1, 2, 90, -50, 150, -300, 56, 12};

    auto seq = getMaxSubSeq(arr);
    while(seq.first != seq.second) {
        std::cout << *(seq.first) << " ";
        ++(seq.first);
    }

    return 0;
}