Maximum sum sublist?

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

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

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

according to the question, in case, if all the elements in the list are negative, it should return maximum sum as 'ZERO'

instead if you want the output as maximum of subarray(in negative number),then the below code will help:

In [21]: def mssl(l):
...:     best = cur = l[0]
...:     for i in range(len(l)):
...:         cur = max(cur + l[i], l[i])
...:         best = max(best, cur)
...:     return best

examples:

In [23]: mssl([-6, -44, -5, -4, -9, -11, -3, -99])
Out[23]: -3
In [24]: mssl([-51, -23, -8, -2, -6])
Out[24]: -2

for both positive and negative numbers

In [30]: mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
Out[30]: 19

So if you understand what a sublist is (or a slice, which can be assumed to be the same thing), the slice is defined by the start index and the end index.

So maybe you could try and iterate over all possible start and end indexes and compute the corresponding sum, then return the maximum one.

Hint: the start index can vary from 0 to len(given_list)-1. The end index can be from start_index to len(given_list)-1. You could use a nested for loop to check all possible combinations.

Here's an implementation in Java, using Kadane’s Algorithm, which prints the indexes of the biggest sum. The implementation takes O(n) time and O(1) space.

public static void maxSumIndexes(int[] a) {

    int size = a.length;
    if(size == 0) return;

    int maxAtIndex = a[0], max = a[0];
    int bAtIndex = 0;
    int b = 0, e = 0;

    for(int i = 1; i < size; i++) {
        maxAtIndex = Math.max(a[i], a[i] + maxAtIndex);
        if(maxAtIndex == a[i])
            bAtIndex = i;

        max = Math.max(max, maxAtIndex);
        if(max == maxAtIndex) {
            e = i;
            b = (b != bAtIndex)? bAtIndex : b;
        }
    }

    System.out.println(b);
    System.out.println(e);
}