0

I am looking at the algorithm used to obtain the maximum sum of a subarray within an array and am unable to understand the logic behind the code. Specifically, this line max_ending = max(0, max_ending + number). I don't understand what is being done here. Also, would this algorithm have a complexity of O(n) or O(n^2)?:

#include <vector>
#include <algorithm>
using namespace std;
template <typename T> T max_sub_array (vector<T> const & numbers)
{
    T max_ending = 0; max_so_far = 0;
    for(auto & number: numbers)
    {
        max_ending = max(0, max_ending + number);
        max_so_far = max(max_so_far, max_ending);
    }
    return max_so_far;
}

Thank You

Improve this question
1
  • 1
    It's simple: you just keep summing. Whenever the sum drops below zero, it means it's best to discard the current value and starting summing again. Commented Sep 21, 2015 at 0:00

4 Answers 4

Reset to default
1

The algorithm you presented seems to be the one attributed (in Wikipedia) to Jay Kadane. The line, max_ending = max(0, max_ending + number), means we are looking only at non-negative sums; in other words, if adding one more element to the current subarray would result in a negative sum, then make the maximum sum ending at this index zero (i.e., the subarray is empty again). The line relies on the idea that the only time we need to reset the examined subarray window is if it drops below zero — even if large positive elements could be added later, a larger subarray sum would be attained without a drop to negative in the middle. Let's look at an example (max_ending means the maximum sum for a subarray ending at the current index):

           {1,2,23,-4,3,-10}
max_ending  1 3 26 22 25 15
max_so_far  1 3 26 26 26 26

Time complexity for this algorithm is assessed as O(n) since each array element needs to be visited once, and the number of iterations is dependent on the array size in a linear fashion. O(n^2) would mean that for each array element, the number of iterations would be on the order of the array size; so as the array size increases, the number of iterations would increase quadratically.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I think you meant quadratic growth and not exponential.
1

This is taken from exercise 4.1-5 of the Introduction to Algorithms Book. Since this question and its answer addresses this. I think this may be helpful.

"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 subarray of A[1.. j] , extend the answer to find a maximum subarray ending at index j + 1 by using the following observation: a maximum subarray of A[1.. j + 1] is either a maximum subarray of A[1.. j] or a subarray A[i .. j +1] , for some 1 <= i<= j + 1. Determine a maximum subarray of the form A[i... j+1] in constant time based on knowing a maximum subarray ending at index j."

Answer First we need to figure out the maximum sub array ending at index j + 1 which could be just A[j + 1] or the maximum subarray ending at j plus A[j+1] , therefore we find the max of this two.

Once we have the maximum sub array ending at index j + 1 we find the maximum of A[1..j+1] by again, getting the max between maximum sub array ending at index j + 1 and maximum subarray of A[1..j].

So basically the idea is getting the maximum sub array ending at the current index of each iteration and getting the max between this and the max of the previous iteration.

Also I think this is incorrect

Edit: This will depend on definition, if the array doesn't need to contain at least one positive number. Otherwise yours is OK. 

max_ending = max(0, max_ending + number);

it should be :

max_ending = max(number, max_ending + number);

Also max_ending and max_so_far should start at numbers[0] and the loop at index 1, if you follow mi change.

The complexity for this algorithm is O(n)

Additional note: In your version there is no need to get the max between number and max_ending + number because max_ending >= 0 so number <= number + max_ending

Improve this answer

3 Comments

max_ending is just for next iteration, his algorithm is correct.
I don't think this corresponds to the definition of the maximum sub array for example the input { -2,-6,-7,-8} should return -2 but returns 0.
it depends if empty sub array is allowed
0

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/

The coding test would help to understand more about what to choose 0 or others for max_ending. As @גלעד ברקן said, it's important decision point whether to discard the slice so far.

Improve this answer

Comments

-1

Let's say sum[i] is the sum of sequence end with numbers[i], then sum[i] = max(numbers[i], numbers[i] + sum[i-1]), the answer is max(sum[i] for i from 0 to numbers.size() - 1)

See Maximum subarray problem

Improve this answer

5 Comments

No, it's not. If, for example, numbers[0] = -1, no value in sum[i] would be the real maximum subarray sum.
@JuanLopes, you just need to initialize max_sum to 0 to compare with all the sum[i]. I am just explaining the main point...
It would still be wrong. You are missing the main point of the algorithm: you must discard the current suffix sum when it drops below zero. If you still don't see, your idea fails for this input: [1, -2, 3].
@JuanLopes sum[0] = 1, sum[1] = -1, sum[2] = 3, I don't see anything wrong. I don't think you understand my answer.
@JuanLopes sum[i] = max(numbers[i], numbers[i] + sum[i-1]), it just depends on sum[i-1] >= 0, it's equivalent to what you said "dropping below zero".

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.