Function to find a subsequence with the largest sum from a list.

subsequence.py

"""
Function to find the contiguous subsequence in a 
list that has the greatest sum.
"""

def max_subsequence(L):
    """
    Implements a linear time algorithm.

    >>> max_subsequence([1,2,3,4,5])
    [1, 2, 3, 4, 5]
    >>> max_subsequence([5,4,3,2,1])
    [5, 4, 3, 2, 1]
    >>> max_subsequence([1,2,3,-4,-5])
    [1, 2, 3]
    >>> max_subsequence([5,4,3,-2,-1])
    [5, 4, 3]
    >>> max_subsequence([-1,-2,3,4,5])
    [3, 4, 5]
    >>> max_subsequence([-5,-4,3,2,1])
    [3, 2, 1]
    >>> max_subsequence([1,2,-3,4,5])
    [4, 5]
    >>> max_subsequence([5,4,-3,2,1])
    [5, 4]
    >>> max_subsequence([-1,-2,3,-4,-5])
    [3]
    >>> max_subsequence([-5,-4,3,-2,-1])
    [3]
    >>> max_subsequence([1,1,1,1,1])
    [1, 1, 1, 1, 1]
    >>> max_subsequence([1,-1,-1,-1,1])
    [1]
    >>> max_subsequence([-1,-1,-1,-1,-1])
    []
    """
    # Max sum subsequence is defined as L[a:b+1]. In other 
    # words, L[a] is the first element, and L[b] is the last 
    # element.
    a = 0
    b = -1

    # The leading subsequence, that is, the max sum subsequence 
    # that includes L[i] starts at L[k] and ends at L[i].
    k = 0
    i = 0

    # Invariant: L[a:b+1] is the subsequence with the greatest 
    # sum in L[0:i+1]. At the same time, L[k:i+1] is the 
    # subsequence with the greatest sum that includes the 
    # element L[i].
    while i < len(L):
        # If L[k] is non-positive, bump it up one.
        if L[k] <= 0:
            k += 1
        # If the leading subsequence sums to zero or less, 
        # set it to the set that contains just L[i], shifting 
        # k forward.
        if sum(L[k:i+1]) <= 0:
            k = i
        
        # If the leading subsequence has a greater sum, 
        # update the max subsequence to match.
        if sum(L[a:b+1]) < sum(L[k:i+1]):
            a = k
            b = i

        i += 1

    return L[a:b+1]


if __name__ == '__main__':
    import doctest
    doctest.testmod()