maximum contiguous subsequence sum

subsum_test.py

# a contiguous sub-sequence is a sequence taken by starting at a start point and taking everything until an end point.
# e.g the sequence [1, 2, 3] has sub sequences [], [1], [2], [3], [1, 2], [2, 3] and [1, 2, 3]
# Given a list of numbers, return the contiguous sub-sequence which has the largest sum (add up all of the numbers)

# eg [1, 2, 3] -> [1, 2, 3]
# [1, -2, 3] -> [3]
# [2, -1, 3] -> [2, -1, 3]
# [-1, 1, 1, 2, -1, 2, -5] -> [1, 1, 2, -1, 2]

# Gotchas:

# We don't need to generate all contiguous sub-sequences
# We can achieve this with O(n) time
# Also O(1) space.

# Solution:

# It makes one pass over the input
# and stores the global max sub-sequence and its sum and also the current sub-sequence and its sum
# Its strategy for finding the current sub-sequence is:

# when we see a new element
# add it to the current sub-sequence,
# if its sum is now negative then...

# this sub sequence can't be the best because choosing nothing is better.
# all the other sub-sequences left of us have been considered because moving the end position has been considered
# and moving the left position of the sub-sequence right couldn't result in a larger sub-sequence sum
# because it would need to remove a sub-sequence of numbers which has a negative sum
#
# if the sum is still positive then...
# see if its the maximum and keep going

def subsum(numbers):
    max_sum = 0
    max_sum_start = 0
    max_sum_end = 0

    current_sum = 0
    current_start = 0
    for i in xrange(len(numbers)):
        current_sum += numbers[i]
        if current_sum < 0:
            current_sum = 0
            current_start = i + 1
            continue
        if current_sum > max_sum:
            max_sum = current_sum
            max_sum_start = current_start
            max_sum_end = i + 1
    return numbers[max_sum_start:max_sum_end]


#########  Tests  ###########


import random
import unittest

import subsequencesum


class TestSubsum(unittest.TestCase):
    def test_subsum(self):
        self.assertEqual(subsequencesum.subsum([1, 2, 3]), [1, 2, 3])
        self.assertEqual(subsequencesum.subsum([1, 2, -3]), [1, 2])
        self.assertEqual(subsequencesum.subsum([-1, 2, 3]), [2, 3])
        self.assertEqual(subsequencesum.subsum([1, -2, 3]), [3])
        self.assertEqual(subsequencesum.subsum([-1, -1, -1]), [])

        self.assertEqual(subsequencesum.subsum([]), [])
        self.assertEqual(subsequencesum.subsum([1]), [1])
        self.assertEqual(subsequencesum.subsum([-1]), [])

        self.assertEqual(subsequencesum.subsum([1, 2, 3, -2, 3, -3]), [1, 2, 3, -2, 3])
        self.assertEqual(subsequencesum.subsum([1, 1, -3, 3, -1, 2, -1]), [3, -1, 2])

        arr = [random.randint(-100, 100) for i in xrange(15000)]
        subsequencesum.subsum(arr)


if __name__ == '__main__':
    unittest.main()