7

I had an interview question a while back that I never got a solution for. Apparently there is a "very efficient" algorithm to solve it.

The question: Given an array of random positive and negative numbers, find the continuous subset that has the greatest sum.

Example:

[1, -7, 4, 5, -1, 5]

The best subset here is {4, 5, -1, 5}

I can think of no solution but the brute-force method. What is the efficient method?

6
  • 1
    See: Programming Pearls
    – Paul R
    Aug 28, 2012 at 19:06
  • 4
    Hint: Modify Kadane's algorithm
    – noMAD
    Aug 28, 2012 at 19:08
  • @noMAD- Doesn't Kadane's algorithm directly solve this problem? Aug 28, 2012 at 19:13
  • @templatetypedef No, it finds the sum. Here we want the indices. hence need to modify it a bit. Simple change though. More pedantic than anything else :)
    – av501
    Aug 28, 2012 at 19:15
  • @templatetypedef: you could compare maxsum() that implements Kadane's algorithm and its modification maxsumseq() that computes indexes and returns the subsequence from Greatest subsequential sum problem.
    – jfs
    Sep 30, 2012 at 13:19

5 Answers 5

4

Iterate through the list, keeping track of the local sum of the list elements so far.
If the local sum is the highest sum so far, then keep a record of it.
If the local sum reaches 0 or below, then reset it and restart from the next element.

Theory

If the current subset sum is greater than zero it will contribute to future subset sums, so we keep it. On the other hand if the current subset sum is zero or below it will not contribute to future subset sums. So we throw it away and start fresh with a new subset sum. Then it's just a matter of keeping track of when the current subset sum is greater then any previous encountered.

Pseudocode

In-parameter is an array list of length N. The result is stored in best_start and best_end.

best_sum = -MAX
best_start = best_end = -1
local_start = local_sum = 0

for i from 0 to N-1 {

    local_sum = local_sum + list[i]

    if local_sum > best_sum {
        best_sum = local_sum
        best_start = local_start
        best_end = i
    }

    if local_sum <= 0 {
        local_sum = 0
        local_start = i+1
    }

}
3
  • Good implementation of Kadane and nice explanation. One note: if all integers in the array happen to be negative and you must select some actual subset of the array (as opposed to the empty set {}), then you must add one last check to pull the negative number closest to zero for this case. (i.e. if given [-3, -7, -1, -2] the answer should be {-1})
    – mVChr
    Dec 23, 2013 at 20:01
  • 1
    My pseudocode actually takes care of that since I initialize best_sum to the largest negative integer (-MAX) (something I could have explained better I agree).
    – Jens Agby
    Jan 15, 2014 at 0:32
  • Well, I'll be! Nice work!
    – mVChr
    Jan 15, 2014 at 2:48
2

Convert the list into a list of cumulative sums, [1,-7,4,5,-1,5] to [1, -6, -2, -3, 2]. Then walk through the list of cumulative sums, saving the smallest value so far and the maximum difference between what you see as the current value and what is currently the smallest value. Got it from here

1

You can answer this question from CLRS, which includes a tip:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem.

Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far.

Knowing a maximum sub array of A[1..j], extend the answer to find a maximum subarray ending at index j+1 by using the following observation:

a maximum sub array of A[1..j+1] is either a maximum sub array of A[1..j] or a sub array A[i..j+1], for some 1 <= i <= j + 1.

Determine a maximum sub array of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j.

max-sum = A[1]
current-sum = A[1]
left = right = 1
current-left = current-right = 1
for j = 2 to n
    if A[j] > current-sum + A[j]
        current-sum = A[j]
        current-left = current-right = j
    else
        current-sum += A[j]
        current-right = j
    if current-sum > max-sum
        max-sum = current-sum
        left = current-left
        right = current-right
return (max-sum, left, right)
1

Too bad Java does not have tuple return type. So, had to print the indices and sum in the method.

public class Kadane {

    public static void main(String[] args) {
        int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
        findMaxSubArray(intArr);
    }

    public static void findMaxSubArray(int[] inputArray){

        int maxStartIndex=0;
        int maxEndIndex=0;
        int maxSum = Integer.MIN_VALUE; 

        int sum= 0;

        for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
            int eachArrayItem = inputArray[currentIndex];

            sum+=eachArrayItem;

            if( eachArrayItem > sum){
                maxStartIndex = currentIndex;    
                sum = eachArrayItem;      
            }
            if(sum>maxSum){
                maxSum = sum;
                maxEndIndex = currentIndex;
            }
        }

        System.out.println("Max sum         : "+maxSum);
        System.out.println("Max start index : "+maxStartIndex);
        System.out.println("Max end index   : "+maxEndIndex);
    }
}

And here is some shameless marketing : I managed to pull together a slide on how this works

1

Here is the java class which runs in linear time

public class MaxSumOfContinousSubset {

    public static void main(String[] args) {
        System.out.println(maxSum(1, -7, 4, 5, -1, 5));
    }

    private static int maxSum (int... nums) {
        int maxsofar = 0;
        int maxhere = 0;
        for (int i = 0; i < nums.length; i++) {
            maxhere =  Math.max(maxhere + nums[i], 0);
            maxsofar = Math.max(maxhere, maxsofar);
        }
        return maxsofar;
    }
}
1
  • An explanation is often more useful than a direct implementation
    – adrianton3
    Sep 30, 2012 at 18:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.