python - 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

Answer 3

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

Answer 4

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.

Answer 5

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);
}

Answer 6

The simple solution is iterate over the list and just try adding up slices till you find the best one. Here I also included the option to return the actual sublist as well, by default this is False. I used defaultdict for this purpose because it is simpler than lookups.

from collections import defaultdict

def mssl(lst, return_sublist=False):
    d = defaultdict(list)
    for i in range(len(lst)+1):
        for j in range(len(lst)+1):
            d[sum(lst[i:j])].append(lst[i:j])
    key = max(d.keys())
    if return_sublist:
        return (key, d[key])
    return key

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

Bonus: List comprehension method:

def _mssl(lst):
    return max( sum( lst[i:j] ) for i in xrange(len(lst)+1) for j in xrange(i, len(lst)+1) )

Answer 7

It's asking you to choose a smaller subsection of a list such that the smaller subsection's sum is the largest.

If the list is all positive [1 2 3] then of course the subsection with the largest sum is just the sum of the entire list [1 2 3] which is 6.

If the list is all negative [-1 -2 -3] then the subsection with the largest sum is nothing [] which has sum 0.

However if the list has some positive and some negative the decision is harder

[1 2 3 -100 3 4 5] you should see [3 4 5] and return 12

[1 2 3 -2 3 4 5] you should use all of it and return 16

Answer 8

I am assuming that this is the question to find a sub-sequence in an array which produces the maximum sum. I encountered this problem while searching for a maximum sum SUBSET problem.

The java implementation for this question:

public static int maximumSumSubSequence(int[] array) {

    if (null == array) {
        return -1;
    }

    int maxSum = Integer.MIN_VALUE;
    int startIndexFinal = 0;
    int endIndexFinal = 0;
    int currentSum = 0;
    int startIndexCurrent = 0;

    for (int i = 0; i < array.length; i++) {
        currentSum += array[i];

        if (currentSum > maxSum) {
            maxSum = currentSum;
            endIndexFinal = i;
            startIndexFinal = startIndexCurrent;
        }
        if (currentSum <= 0) {
            currentSum = 0;
            startIndexCurrent = i + 1;
        }
    }
    System.out.println("startIndex: " + startIndexFinal + " endIndex: " + endIndexFinal);
    return maxSum;
}

Answer 9

This distinction probably isn't important to the OP, who seems to be just trying to understand how to solve the problem at all, but I thought it was worth mentioning:

The other solutions here involve repeatedly summing up all the subparts of the list. We can avoid these repeated sums by using dynamic programming, since of course if we already know the sum from i to j we don't need to do add them up again to get the sum from i to j+1!

That is, make a 2d array of the partial sums, so that partsum[i, j] == sum(lst[i:j]). Something like (using a dictionary because it's easier to index with; a numpy array would be equally easy and more efficient):

import operator

def mssl(lst, return_sublist=False):
    partsum = { (0, 0): 0 }  # to correctly get empty list if all are negative
    for i in xrange(len(lst) - 1):  # or range() in python 3
        last = partsum[i, i+1] = lst[i]
        for j in xrange(i+1, len(lst)):
            last = partsum[i, j+1] = last + lst[j]

    if return_sublist:
        (i, j), sum = max(partsum.iteritems(), key=operator.itemgetter(1))
        return sum, lst[i:j]

    return max(partsum.itervalues())  # or viewvalues() in 2.7 / values() in 3.x

This takes O(n^2) time and memory, as opposed to O(n^3) time and O(1) memory for Lev/Inbar's approach (if not implemented sillily like Inbar's first code example).

Answer 10

This post introduces three ways to find the maximum subarray of an array.

• Brute force (O(n*n))
• Divide and conquer (O(nlgn))
• Kadane's algorithm (O(n))

Among them, the fastest one is the Kadane's algorithm which has a time complexity of O(n).

Answer 11

if someone is looking for a longer version of a code, here it is:

def mesl(lst):
    sub_sum = list()
    row_sum = list()
    for i in range(len(lst)):
        sub_sum = list()
        sub_sum.append(lst[i])
        k = 1
        for j in range(i+1,len(lst)):
            sub_sum.append(sub_sum[k-1] + lst[j])
            k+=1
        row_sum.append(max(sub_sum))      
    sum = max(row_sum)
    if  sum < 0:
        sum = 0
    return sum

Answer 12

I am presenting a Dynamic Programming based approach. The main idea is that as we iterate through the array, adding a new element to our current sum-value should either increase the value of the sum, or, we go ahead with our current element and forget the old sum-value.

To accommodate arrays with negative values, we instantiate our variables with the first element of the array.

def maxSumSubArr(arr):
    cur_sum = best_sum = arr[0]
    for i in range(1, len(arr)):
        cur_sum = max(arr[i], cur_sum+arr[i])
        best_sum = max(best_sum, cur_sum)
    return best_sum

The running time of this approach is O(n), and the space complexity is O(1).

If you want the output to be zero for the cases where none of the elements are positive, then instantiate the cur_sum and best_sum variables with 0 and iterate from the first element instead of the second element.

Answer 13

Here is the shortest and best solution in javascript to the maximum subarray problem:

var maxSubArray = function(nums) {
    for (let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    }
    return Math.max(...nums);
};