Maximum sum sublist?

by

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

More Related Contents:

  1. python algorithm, find duplicates in list [closed]
  2. How can we develop an algorithm to solve a problem of DP [closed]
  3. Elegant Python code for Integer Partitioning [closed]
  4. What is the most efficient way of finding all the factors of a number in Python?
  5. Is the time-complexity of iterative string append actually O(n^2), or O(n)?
  6. Quicksort with Python
  7. Generate all permutations of a list without adjacent equal elements
  8. how to split an iterable in constant-size chunks
  9. How do I generate all permutations of a list?
  10. Modular multiplicative inverse function in Python
  11. Representing and solving a maze given an image
  12. Merging a list of time-range tuples that have overlapping time-ranges
  13. Python program to check matching of simple parentheses
  14. Python Implementations of Packing Algorithm
  15. Gauss-Legendre Algorithm in python
  16. Subset sum Problem
  17. Compute *rolling* maximum drawdown of pandas Series
  18. all permutations of a binary sequence x bits long
  19. What algorithm does Python’s built-in sort() method use?
  20. How to split an iterable into two lists with alternating elements
  21. How can I match up permutations of a long list with a shorter list (according to the length of the shorter list)? [duplicate]
  22. Where can I find source or algorithm of Python’s hash() function?
  23. Python: maximum recursion depth exceeded while calling a Python object
  24. How do I fix wrongly nested / unclosed HTML tags?
  25. Python pi calculation?
  26. Sieve of Eratosthenes – Primes between X and N
  27. How can I fit a Bézier curve to a set of data?
  28. Mergesort with Python
  29. Find non-common elements in lists
  30. Algorithm for solving Sudoku

Leave a Comment