Find the maximum interval sum in a list of real numbers

Question

Here's an interview questions that a colleague asked for a programming position. I thought this was great for watching the interviewee think it through. I'd love to get responses for how the SO community thinks of it.

Given a list of real numbers of length N, say [a_1, a_2, ..., a_N], what is the complexity of finding the maximum value M for which there exist indices 1 <= i <= j <= N such that

a_i + a_{i+1} + ... + a_j = M?

My apologies if this is a classic CS problem.

Answer 1

We can just use the easiest 2 lines of code algo, it's simple and handles all negative as well :)

curr_max = max(a[i], curr_max+a[i]);

max_so_far = max(max_so_far, curr_max;

eg. C++

int maxSubArraySum(int a[], int size) 
{ 
    int max_so_far = a[0]; 
    int curr_max = a[0]; 

    for (int i = 1; i < size; i++) 
    { 
         curr_max = max(a[i], curr_max+a[i]); 
         max_so_far = max(max_so_far, curr_max; 
    }  
    return max_so_far; 
 } 

Answer 2

I would add an answer that contains 2 approaches, that handle array with or without positive elements differently, written in Java.

---

Code - Java

MaxSubSum.java:

public class MaxSubSum {
    /**
     * Find max sub array, only include sub array with positive sum.
     * <p>For array that only contains non-positive elements, will choose empty sub array start from 0.
     * <p>For empty input array, will choose empty sub array start from 0.
     *
     * @param arr input array,
     * @return array of length 3, with elements as: {maxSum, startIdx, len};
     * <p>tips: should use 'len' when loop the returned max sub array, so that it could also work for empty sub array,
     */
    public static int[] find(int[] arr) {
        if (arr.length == 0) return new int[]{0, 0, 0}; // empty array, no sub array,

        int maxSum = 0;    // max sum, found so far,
        int maxStart = 0;  // start of max sum,
        int maxLen = 0;    // length of max subarray,

        int sum = 0;  // current sum,
        int start = 0;    // current start,

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) { // get a positive,
                if (sum <= 0) {  // should restart,
                    start = i;
                    sum = arr[i];
                } else sum += arr[i];

                if (sum > maxSum) { // get a larger sum,
                    maxSum = sum;
                    maxStart = start;
                    maxLen = i - start + 1;
                }
            } else sum += arr[i]; // 0 or negative number,
        }

        return new int[]{maxSum, maxStart, maxLen};
    }

    /**
     * Find max sub array, also include sub array with non-positive sum.
     * <p>For array that only contains non-positive elements, will choose first smallest element.
     * <p>For empty input array, will choose empty sub array start from 0.
     *
     * @param arr input array,
     * @return array of length 3, with elements as: {maxSum, startIdx, len};
     * <p>tips: should use 'len' when loop the returned max sub array, so that it could also work for empty sub array,
     */
    public static int[] findIncludeNonPositive(int[] arr) {
        if (arr.length == 0) return new int[]{0, 0, 0}; // empty array, no sub array,

        int maxSum = arr[0];    // max sum, found so far,
        int maxStart = 0;    // start of max sum,
        int maxLen = 1;    // length of max subarray,

        int sum = arr[0];  // current sum,
        int start = 0;    // current start,

        for (int i = 1; i < arr.length; i++) {
            if (sum <= 0) { // should restart,
                start = i;
                sum = arr[i];
            } else sum += arr[i];

            if (sum > maxSum) { // get a larger sum,
                maxSum = sum;
                maxStart = start;
                maxLen = i - start + 1;
            }
        }

        return new int[]{maxSum, maxStart, maxLen};
    }
}

MaxSubSumTest.java:
(Test case, via TestNG)

import org.testng.Assert;
import org.testng.annotations.Test;

import java.util.Arrays;

public class MaxSubSumTest {
    @Test
    public void test_find() {
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{-2, -3, 4, -1, -2, 1, 5, -3}), new int[]{7, 2, 5})); // max sub array: {4, -1, -2, 1, 5}
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{12, 14, 0, -4, 61, -39}), new int[]{83, 0, 5})); // max sub array: {12, 14, 0, -4, 61}

        // corner
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{}), new int[]{0, 0, 0})); // empty array,

        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{-5, -4, 0, 0, -7, 0, -2}), new int[]{0, 0, 0})); // array with all elements <= 0,
        Assert.assertTrue(Arrays.equals(MaxSubSum.find(new int[]{-5, -4, -2, -7, -2, -9}), new int[]{0, 0, 0})); // array with all elements < 0,
    }

    @Test
    public void test_findIncludeNonPositive() {
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{-2, -3, 4, -1, -2, 1, 5, -3}), new int[]{7, 2, 5})); // max sub array: {4, -1, -2, 1, 5}
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{12, 14, 0, -4, 61, -39}), new int[]{83, 0, 5})); // max sub array: {12, 14, 0, -4, 61}

        // corner
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{}), new int[]{0, 0, 0})); // empty array,

        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{-5, -4, 0, 0, -7, 0, -2}), new int[]{0, 2, 1})); // array with all elements <= 0,
        Assert.assertTrue(Arrays.equals(MaxSubSum.findIncludeNonPositive(new int[]{-5, -4, -2, -7, -2, -9}), new int[]{-2, 2, 1})); // array with all elements < 0,
    }
}

Explanation:

• find()
  Find max sub array, only include sub array with positive sum.
  Behavior:

  • For array that only contains non-positive elements, will choose empty sub array start from 0.
  • For empty input array, will choose empty sub array start from 0.

  BTW:

  • It restart only when get a positive element, and sum <= 0.

• findIncludeNonPositive()
  Find max sub array, also include sub array with non-positive sum.
  Behavior:

  • For array that only contains non-positive elements, will choose first smallest element.
  • For empty input array, will choose empty sub array start from 0.

  BTW:

  • It restart whenever previous sum <= 0.
  • It prefer sub array start from smaller index, when there are multiple max sub array.
  • It won't include unnecessary 0 at end of sub array, which doesn't change the sum.

Complexity:

• Time: O(n)
• Space: O(1)

Answer 3

I have tried and tested this. In case all numbers are negative, it returns the greatest negative number.

Test cases:

{-5, -1, -2, -3, -4}
{ 12, 14, 0, -4, 61, -39}
{2, -8, 3, -2, 4, -10}

Code:

public int FindLargestSum(int[] arr)
{
    int max = Integer.MIN_VALUE;
    int sum = 0;

        for(int i=0; i < arr.length; i++)
        {   
            if(arr[i] > max) max = arr[i];

            sum += arr[i];

            if(sum < 0)
                sum = 0;
            else if(sum > max)
                max = sum;
        }

    return max;
}

Answer 4

I'm intruding on this ancient thread to give a detailed explanation of why Kadane's algorithm works. The algorithm was presented in a class I'm currently taking, but with only a vague explanation. Here's an implementation of the algorithm in Haskell:

maxCont l = maxCont' 0 0 l

maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
  | newSum > maxSum = maxCont' newSum newSum xs
  | newSum < 0      = maxCont' maxSum 0 xs
  | otherwise       = maxCont' maxSum newsum xs
  where
    newSum = thisSum + x

Now since we're just trying to understand the algorithm, let's undo the minor optimization of naming newSum:

maxCont l = maxCont' 0 0 l

maxCont' maxSum _ [] = maxSum
maxCont' maxSum thisSum (x:xs)
  | thisSum + x > maxSum = maxCont' (thisSum + x) (thisSum+x) xs
  | thisSum + x < 0      = maxCont' maxSum 0 xs
  | otherwise            = maxCont' maxSum (thisSum+x) xs

What is this crazy function maxCont'? Let's come up with a simple specification of what it's supposed to be doing. We want the following to hold, with the precondition that 0 ≤ thisSum ≤ maxSum:

maxCont' maxSum thisSum [] = maxSum
maxCont' maxSum thisSum l  = maximum [maxSum, thisSum + maxInit l, maxCont l]

where maxInit l is the greatest sum of an initial segment of l and maxCont is the maximum contiguous sum of l.

Trivial but important fact: for all l, maxInit l ≤ maxCont l. It should be obvious that the above specification guarantees maxCont l = maxCont' 0 0 l, which is what we want. Instead of trying to explain directly why the final version of maxCont' implements the specification above (which I don't really know how to do), I will show how it can be derived from it, transforming the specification one step at a time until it becomes the code, which will then certainly be correct. As written, this specification doesn't give an implementation: if maxCont is defined in terms of maxCont' as described above, it will loop forever as maxCont' calls maxCont calls maxCont' with the same list. So let's expand it out just a bit to expose the pieces we will need:

maxCont' maxSum thisSum (x:xs) =
                     maximum [maxSum, thisSum + maxInit (x:xs), maxCont (x:xs)]

This didn't fix anything yet, but it exposed things. Let's use that. thisSum + maxInit (x:xs) is either thisSum or thisSum + x + maxInit xs. But thisSum ≤ maxSum by the precondition, so we can ignore this possibility when calculating the maximum. maxCont (x:xs) is a sum that either includes x or doesn't. But if it includes x, then it's the same as maxInit (x:xs), which is covered by the preceding, so we can ignore that possibility, and only consider the case where maxCont (x:xs) = maxCont xs. So we arrive at the next version:

maxCont' maxSum thisSum (x:xs) = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

This one, finally, is properly recursive, but we have a ways to go to get to efficient code, especially because that mythical maxInit would be too slow. Let's break it down into the three cases considered in the Java code (abusing Haskell notation a bit):

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

In the first case, we know that maxSum can't be the maximum: thisSum+x is greater and maxInit xs is always positive. In the second case, we know that thisSum+x+maxInit xs can't be the maximum: maxCont xs is always at least as large as maxInit xs, and thisSum+x is negative. So we can eliminate those possibilities:

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [        thisSum+x+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum,                       maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum, thisSum+x+maxInit xs, maxCont xs]

Now we have just barely enough of an edge to twist things around. Now that we've eliminated impossible cases, we're going to add some duplicate cases, which will put these three cases back into the same form so we can substitute in the original specification of maxCont'. In the first case, we don't have a first term, so we need to use something that we know won't exceed the other terms. To maintain the invariant that thisSum ≤ maxSum, we will need to use thisSum+x. In the second case, we don't have a second term that looks like something+maxInit xs, but we know that maxInit xs ≤ maxCont xs, so we can safely stick in 0+maxInit xs. Adding these extra terms for regularity yields the following:

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maximum [(thisSum+x), (thisSum+x)+maxInit xs, maxCont xs]
  | thisSum + x < 0          = maximum [maxSum,      0+maxInit xs,           maxCont xs]
  | 0 ≤ thisSum + x ≤ maxSum = maximum [maxSum,      thisSum+x+maxInit xs,   maxCont xs]

Finally, having checked the precondition, we substitute in the specification,

maxCont' maxSum thisSum l = maximum [maxSum, thisSum + maxInit l, maxCont l]

to get

maxCont' maxSum thisSum (x:xs)
  | maxSum < thisSum + x     = maxCont' (thisSum+x) (thisSum+x) xs
  | thisSum + x < 0          = maxCont' maxSum 0 xs
  | 0 ≤ thisSum + x ≤ maxSum = maxCont' maxSum (thisSum+x) xs

Fixing this up into real syntax and tacking on the omitted base case yields the actual algorithm, which we've now proven satisfies the spec as long as it terminates. But each successive recursive step operates on a shorter list, so it does indeed terminate.

There's just one last thing to do, for my sake, which is to write the final code more idiomatically and flexibly:

maxCont :: (Num a, Ord a) => [a] -> a
maxCont = fst . foldl maxCont' (0,0)
  where
    maxCont' (maxSum, thisSum) x
      | maxSum < newSum = (newSum, newSum)
      | newSum < 0      = (maxSum, 0)
      | otherwise       = (maxSum, newSum)
      where newSum = thisSum + x

Answer 5

This is a classical, well known, problem that is an excellent eye-opener in any algorithm course. It is hard to find a better/simpler starter. You can find an n*3-, n*2-, nlogn- and even the simple n-algorithm.

I found the problem discussed/solved in John Bentley´s "Programming Pearls" from 1986 - and did use it for years as a starter in our Algorithm Course at NTNU/Trondheim. Some 20 years ago I first used it in an examination for about 250 students, where just 1 student did discover all the 4 solutions, see above. He, Bjørn Olstad, became the "youngest professor ever" at NTNU in Trondheim, and has still this status beside heading the MSFT search division in Oslo. Bjørn also took the challenge to find good practical applications of the algorithm. Do you see some?

• Arne Halaas

Answer 6

Try this code .. it would work fine for at least one +ve number in the array.. O(n) just one for loop used..

public static void main(String[] args) {
    int length ;
    int a[]={-12, 14, 0, -4, 61, -39};  
    length=a.length;

    int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0;
    for (int index=0;index<length;index++) {
        localMax= localMax + a[index];
        if(localMax < 0){ localMax=0; tempStartIndex = index + 1;}
        if(absoluteMax < localMax) {
            absoluteMax = localMax; 
            lastIndex =index; 
            startIndex=tempStartIndex;
        }
    }

    System.out.println("startIndex  "+startIndex+"  lastIndex "+ lastIndex);    
    while (startIndex <= lastIndex) {
        System.out.print(" "+a[startIndex++]);
    }
}

Answer 7

It's O(N):

int sum = 0;
int M = 0;  // This is the output
foreach (int n in input)  {
  sum += n;
  if (sum > M)
      M = sum;

  if (sum < 0)
    sum = 0;
}

The idea is to keep the sum of all integers that have been encountered since last reset. A reset occurs when the sum goes below zero - i.e. there are too many negative numbers in the current interval to make it possibly the best one.

Answer 8

This might be wrong because it's suspiciously simple.

1. Start summing all the elements from 0 to n, and determine the index where the rolling sum was the highest. This will be the upper boundary of your interval.
2. Do the same backwards to get your lower boundary. (It's enough if you start from the upper boundary.)

This looks like O(n).

Answer 9

The complexity is just O(n) for Kadane's algorithm:

The algorithm keeps track of the tentative maximum subsequence in (maxSum, maxStartIndex, maxEndIndex). It accumulates a partial sum in currentMaxSum and updates the optimal range when this partial sum becomes larger than maxSum.