Maximum sum sublist?

Question

I'm getting confused with this question at what it's trying to ask.

Write function mssl() (minimum sum sublist) that takes as input a list of integers. It then computes and returns the sum of the maximum sum sublist of the input list. The maximum sum sublist is a sublist (slice) of the input list whose sum of entries is largest. The empty sublist is defined to have sum 0. For example, the maximum sum sublist of the list [4, -2, -8, 5, -2, 7, 7, 2, -6, 5] is [5, -2, 7, 7, 2] and the sum of its entries is 19.

If I were to use this function it should return something similar to

>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5] >>> mssl(l) 19 >>> mssl([3,4,5]) 12 >>> mssl([-2,-3,-5]) 0 

How can I do it?

Here is my current try, but it doesn't produce the expected result:

def mssl(x):     ' list ==> int '     res = 0     for a in x:         if a >= 0:             res = sum(x)         return res     else:         return 0 

Answer 1

There's actually a very elegant, very efficient solution using dynamic programming. It takes O(1) space, and O(n) time -- this can't be beat!

Define A to be the input array (zero-indexed) and B[i] to be the maximum sum over all sublists ending at, but not including position i (i.e. all sublists A[j:i]). Therefore, B[0] = 0, and B[1] = max(B[0]+A[0], 0), B[2] = max(B[1]+A[1], 0), B[3] = max(B[2]+A[2], 0), and so on. Then, clearly, the solution is given simply by max(B[0], ..., B[n]).

Since every B value depends only on the previous B, we can avoid storing the whole B array, thus giving us our O(1) space guarantee.

With this approach, mssl reduces to a very simple loop:

def mssl(l):     best = cur = 0     for i in l:         cur = max(cur + i, 0)         best = max(best, cur)     return best 

Demonstration:

>>> mssl([3,4,5]) 12 >>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5]) 19 >>> mssl([-2,-3,-5]) 0 

---

If you want the start and end slice indices, too, you need to track a few more bits of information (note this is still O(1) space and O(n) time, it's just a bit hairier):

def mssl(l):     best = cur = 0     curi = starti = besti = 0     for ind, i in enumerate(l):         if cur+i > 0:             cur += i         else: # reset start position             cur, curi = 0, ind+1          if cur > best:             starti, besti, best = curi, ind+1, cur     return starti, besti, best 

This returns a tuple (a, b, c) such that sum(l[a:b]) == c and c is maximal:

>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5]) (3, 8, 19) >>> sum([4, -2, -8, 5, -2, 7, 7, 2, -6, 5][3:8]) 19 

Answer 2

This is the maximum sub-array problem. The Kadane's algorithm can solve it in O(n) time and O(1) space, and it goes as follows:

def mssl(x):     max_ending_here = max_so_far = 0     for a in x:         max_ending_here = max(0, max_ending_here + a)         max_so_far = max(max_so_far, max_ending_here)     return max_so_far