CODEWITHSUNDEEP
pythonalgorithmsequencedynamic-programming
randomUser47534
randomUser47534

Reputation: 329

Maximum sum contiguous subsequence is zero?

I am attempting to understand the solution to this problem: "Given a sequence of numbers, find the maximum sum of a contiguous subsequence of those numbers." I have quoted a solution and explanation below.

What I don't understand is, in the line "maxendinghere = max(maxendinghere + s, 0)", why would maxendinghere ever be zero? 

def max_sum_subsequence(seq):
    maxsofar = 0
    maxendinghere = 0
    for s in seq:
        # invariant: maxendinghere and maxsofar are accurate
        # are accurate up to s
        maxendinghere = max(maxendinghere + s, 0)
        maxsofar = max(maxsofar, maxendinghere)
    return maxsofar

The explanation from the website is "Well, essentially maxendinghere is what’s accumulating the subsequences — it keeps rolling the next element into itself. Should this accumulated sum ever become negative we know that the subsequence-which-ends-here we’re currently tracking is worse than the empty subsequence-which-restarts-here; so we can reset our subsequence accumulator, and the first clause of the loop invariant still holds."

What I don't understand is, let's say my sequence is 2 -3 4: why would maxendinghere ever be zero? There is no subsequence whose sum is zero.

(Quotes from: http://wordaligned.org/articles/the-maximum-subsequence-problem)

Upvotes: 0

Views: 547

Answers (1)

Shashank
Shashank

Reputation: 13869

In your example 2 -3 4, ask yourself, what is the maximum sum that ends at index 1? 2 - 3 is -1. -3 itself is -3. So our maximum sum is then the empty sum, which selects no elements and therefore has a sum of 0.

Remember that the empty subsequence is always a possibility, and the identity value of the sum operation is 0. So for example, the maximum sum of a contiguous subsequence within -2 -4 -3 is simply 0, the sum of the empty subsequence.

To validate this:

>>> max_sum_subsequence([-2, -4, -3])
0
>>> sum([]) == 0
True

To change the algorithm so that the subsequence must have at least length 1, you can do so by changing two lines of code.

First, change the initialization of maxsofar to be the first element or None if it doesn't exist. Instead of None, you can use any default value of your choice. The default value is what gets returned for an empty input sequence.

maxsofar = seq and seq[0] or None

Second, change the assignment to maxendinghere to force it to include the value of at least one element from the sequence:

maxendinghere = max(maxendinghere + s, s)

Upvotes: 2

Related Questions