Random integers in array. Find the greatest sum of a continuous subset [duplicate]

Question

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?

Answer 1

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
    }

}