Python: Minimum Sum Sublist of an Integer

Question

Python Trouble: I am having so much trouble on how to approach this program. Can someone help me or at least give me a hint on what this program is asking?

5.37 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.
>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
>>> mssl(l)
19
>>> mssl([3,4,5])
12
>>> mssl([-2,-3,-5])
0

Ah-ha so you did - must remember to get myself glasses at some point :) — Jon Clements

sloth sloth · Accepted Answer · 2013-02-25T15:30:04

First, you are asked to find all possible sublists of your list. Given your list is [3,4,5], all possible sublists are:

[]
[3]
[3,4]
[3,4,5]
[4]
[4,5]
[5]

You can do this using a nested loop and slicing:

l = your_list
for start in xrange(len(l)):
  for end in xrange(1, len(l)+1):
    current_sublist = l[start:end]

Next, you are tasked to find the maximum sum of any of those sublists. One way is to create a local variable update it in the loop if the sum of the current sublist is greater than any sum before. Let's also wrap it into a function:

def mssl(l):
  f = 0
  for start in xrange(len(l)):
    for end in xrange(1, len(l)+1):
      s = sum(l[start:end]) 
      if s > f: 
        f = s
  return f

Let's test it:

print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
print mssl([3,4,5])
print mssl([-2,-3,-5])

Output:

19
12
0

one-liner for good measure:

l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
max(sum(l[s:e]) for s in xrange(len(l)) for e in xrange(1, len(l)+1))

Python: Minimum Sum Sublist of an Integer

1 Answers