Maximum Value Contiguous Subsequence. Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized. http://people.csail.mit.edu/bdean/6.046/dp/

max_sum_seq.py

import pytest

class MaxSumSeq:
    def __init__(self, A):
        assert A
        self.A = A
        self.n = len(A)
        self.tab = [None for i in range(self.n)]
        self.tab[0] = self.A[0]

    def M(self, i):
        '''Find the maximum seq sum ending at position i'''
        if self.tab[i] != None: return self.tab[i]
        prev = self.tab[i-1]
        if prev >= 0:
            self.tab[i] = prev + self.A[i]
        else:
            self.tab[i] = self.A[i]
        return self.tab[i]

    def solve(self):
        if not self.A: return ()
        maxi = max(range(self.n), key=self.M)
        if maxi == 0: return (self.M(maxi), (0,0))
        cur = maxi - 1
        start = -1
        while cur >= 0:
            if self.M(cur) < 0:
                start = cur + 1
                break
            cur -= 1
        if start == -1: start = 0
        return (self.M(maxi), (start, maxi))

class TestMaxSumSeq:
    def test_empty(self):
        with pytest.raises(AssertionError):
                MaxSumSeq([]).solve()

    def test_normal(self):
        assert MaxSumSeq([1,2,3,4]).solve() == (10, (0,3))

    def test_normal2(self):
        assert MaxSumSeq([0]).solve() == (0, (0,0))

    def test_normal3(self):
        assert MaxSumSeq([-1,1]).solve() == (1, (1,1))

    def test_normal4(self):
        assert MaxSumSeq([1,1]).solve() == (2, (0,1))

    def test_normal5(self):
        assert MaxSumSeq([3,-1,1,5,-6]).solve() == (8, (0,3))