Find the maximum sum of an interval in a list of real numbers

Question

Here, the interview asks that a colleague requested a programming position. I thought it was great to watch how the interlocutor experiences this. I'd love to get answers to a question about how the SO community thinks about it.

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

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

My apologies if this is a classic CS issue.

Answer 1

The complexity is only O (n) for the Kadane algorithm :

The algorithm tracks the preliminary maximum subsequence in (maxSum, maxStartIndex, maxEndIndex) . It accumulates a partial amount in currentMaxSum and updates the optimal range when this partial amount becomes larger than maxSum .

Answer 2

This is 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 the integers that have been met since the 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 possible better.

Answer 3

This is a classic, well-known problem, which is an excellent opening for the eyes in any course of the algorithm. It is hard to find a better / simpler starter. You can find n * 3-, n * 2-, nlogn- and even a simple n-algorithm.

I found that the issue was discussed / resolved in John Bentley's Pearl Programming since 1986 - and used it for many years as a starter in our NTNU / Trondheim Algorithms course. About 20 years ago, I first used it in an exam of about 250 students, where only one student found all 4 solutions, see above. He, Björn Olstad, became the “youngest professor ever” at NTNU in Trondheim and still has this status next to the MSFT search division in Oslo. Bjorn also tried to find good practical applications of the algorithm. Do you see some?

• Arne Halas

Answer 4

Try this code .. it will work fine for at least one + ve number in the array. O (n) is used only one for the used cycle.

 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 5

This may be wrong because it is suspiciously simple.

• Start summing all the elements from 0 to n and determine the index where the maximum roll amount is. This will be the upper limit of your interval.
• Do the same back to get your bottom border. (This is sufficient if you start from the top border.)

It looks like O (n).

Answer 6

I invade this ancient thread to give a detailed explanation of why the Kadane algorithm works. The algorithm was presented in a class that I am currently accepting, but with an indefinite explanation. Here's the 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 are just trying to understand the algorithm, we’ll newSum small newSum 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 maxCont' function? Let me come up with a simple specification of what it should do. We want the following condition to be satisfied: 0 ≤ thisSum ≤ maxSum :

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

where maxInit l is the largest sum of the initial segment l , and maxCont is the maximum continuous sum l .

A 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 what we want. Instead of directly explaining why the final version of maxCont 'implements the above specification (that I really don’t know how to do it), I will show how it can be obtained from it by transforming the specification one step at a time until it becomes code that will certainly be correct. As written, this specification does not provide an implementation: if maxCont is defined in terms of maxCont' , as described above, it will be cyclically forever, since maxCont' calls maxCont calls maxCont' with the same list. So let me expand it a bit to expose the fragments we need:

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

It hasn't fixed anything yet, but it exposed things. Let me use it. thisSum + maxInit (x:xs) - either thisSum or thisSum + x + maxInit xs . But thisSum ≤ maxSum by assumption, so we can ignore this possibility when calculating the maximum. maxCont (x:xs) is a sum that either includes x or not. But if it includes x , then it coincides with maxInit (x:xs) , which is covered by the previous one, so we can ignore this possibility and consider only the case when maxCont (x:xs) = maxCont xs . So, we come to the next version:

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

This one is finally correctly recursive, but we have ways to move to efficient code, especially because this mythical maxInit will be too slow. Let me break it down into three cases discussed in Java code (a bit of abuse of Haskell notations):

 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 cannot be maximal: thisSum+x greater, and maxInit xs always positive. In the second case, we know that thisSum+x+maxInit xs cannot be maximal: maxCont xs always no less than maxInit xs , and thisSum+x negative. Therefore, we can eliminate these 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 barely have enough edges to twist around. Now that we have eliminated the impossible cases, we will add a few recurring cases that will return these three cases to the same form so that we can replace the original maxCont' specification. In the first case, we do not have the first term, so we need to use something that, as we know, will not exceed other conditions. To preserve the invariant that thisSum ≤ maxSum , we will need to use thisSum+x . In the second case, we don’t have a second member that looks like something+maxInit xs , but we know that maxInit xs ≤ maxCont xs , so we can safely stick to 0+maxInit xs . Adding these additional 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, after checking the precondition, we substitute it into the specification

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

To obtain

 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 in real syntax and binding to a missing base register gives a real algorithm, which, as we have now proved, satisfies the specification until it ends. But each subsequent recursive step works in a shorter list, so it really ends.

Here is just one thing for me, 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 7

I have tried and tested this. If all numbers are negative, it returns the largest negative number.

Test cases:

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

the 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 8

I would like to add an answer that contains 2 approaches that handle the array in different ways with or without positive elements, 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 the maximum subarray, include only the subarray with a positive sum.
  Behavior:

  • For an array that contains only non-positive elements, an empty sub-array will be selected, starting at 0.
  • For an empty input array, select an empty subarray starting at 0.

  BTW:

  • It is restarted only when a positive item is received, and the sum is <= 0.

• findIncludeNonPositive()
  Find the maximum nested array, also include the nested array with a non-positive sum.
  Behavior:

  • For an array that contains only non-positive elements, I will select the first smallest element.
  • For an empty input array, select an empty subarray starting at 0.

  BTW:

  • It restarts whenever the previous sum is <= 0.
  • He prefers the subarray to start at a lower index when there are several maximum subarrays.
  • It will not contain unnecessary 0 at the end of the subarray, which does not change the amount.

Complexity:

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