General
Given a list of integers, return the contiguous subsequence with the highest sum:
For example, given a list of integers, like:
>>> my_list = [1, 0, 3, -8, 4, -2, 3]
Return the contiguous subsequence with the largest sum. For that example, the answer would be [4, -2, 3], which sums to 5.
Some other examples:
>>> largest_sum([1, 0, 3, -8, 4, -2, 3])
[4, -2, 3]
>>> largest_sum([1, 0, 3, -8, 4, -2, 3, -2])
[4, -2, 3]
>>> largest_sum([1, 0, 3, -8, 19, -20, 4, -2, 3, -2])
[19]
For ties, return the first one:
>>> largest_sum([2, 2, -10, 1, 3, -20])
[2, 2]
Return the shortest version:
>>> largest_sum([2, -2, 3, -1])
[3]
If the list is all negative numbers, the subsequence with the highest sum will be empty (ie, we can do no better than pick nothing!):
>>> largest_sum([-1, -2])
[]
Challenge
You could do this in a very slow way by trying every possible subsequence, but the runtime here would be poor (what would the runtime be?)
There’s a way to do this with a runtime of O(n), but it requires some careful thinking.
We’ve provided a file, largestsum.py, with a function, largest_sum:
def largest_sum(nums):
"""Find subsequence with largest sum."""
Implement this function.
“Best” and Giving Up
You can do this in O(n) by looping through the list, keeping track of the sum so far, and comparing this to the best sum you’ve seen.
There’s a good way to know when to “give up” on a subsequence—when the sum goes below 0.
For example, given:
[2, 2, -10, 1, 5, -20, 5]
You’ll start with a sum of 0 (nothing in our list yet!), add 2, add 2 more for 4, but then lose 10 for -6. At this point, you know that it will never be advantageous to keep this work, since it will always be better to just start over at the next number.
Then, starting over with 1 and adding 5, you get 6. Adding -20 will drop you below 0 so you again know you could give up.
Starting over at 5, you’d end up with 5, which is less than the best you’ve seen so far, 6.