Given a list on integers (positive and negative), return the sum of the continues subsequence with largest sum

largest_subsequence.py

"""
Given a list on integers (positive and negative), return the sum of the
continues subsequence with largest sum
"""


def largest_subsequence(sequence):
    """
    The solution depends on ignoring the sum sequence(j -> i)
    if sequence[i+1] > sum sequence(j -> i+1) where j < i and 0 <= i, j < n

    Time complexity = O(n)
    Space complexity = O(n)

    """
    max_subsequence, local_max_subsequence = sequence[0], sequence[0]
    for i in sequence[1:]:
        local_max_subsequence = max(local_max_subsequence + i, i)
        max_subsequence = max(local_max_subsequence, max_subsequence)
    return max_subsequence

if __name__ == '__main__':
    # Result 21
    print largest_subsequence([1, 2, 3, 4, -6, -8, 6, 7, 8, -4])
    # Result -1
    print largest_subsequence([-1, -2, -3, -4, -6, -8, -6, -7, -8, -4])