The above formula take in a sequence, i, and j, and tell the score of overlapped region. i and j is the starting and ending index of subsequence in the master sequence.

For example, given a sequence \{1, -2, 0, 3, -1, 0, 2, -3\}, the maximum contiguous sebsequence is \{3, -1, 0, 2\}, another is \{0, 3, -1, 0, 2\}. Thus the score MCSS(a) = 3 - 1 + 0 + 2 = 0 + 3 - 1 + 0 + 2 = 4

Maximum Contiguous-Subsequence-Sum (MCSS) Problem: finding the contiguous subsequence of the sequence with maximum total sum (bigges)

We define the MCSS of an empty sequence to be 0. Since the empty sequence is a contiguous subsequence of any sequence

Bruteforce MCSS

There are n^2 possible contiguous subsequence because there are n possible values of starting point and n possible values of ending points. Array formulation for calculating the sum is O(n), so brute force algorithm will take O(n^3)

Hint: actually, computing the sum can be amortized to O(n^2) if you try all possible subsequences.

Kadane's Algorithm

Kadane's Algorithm

we assume the subsequence start at index 0, initialize a current maximum to 0 and starting and ending index of how to get the maximum sum

we calculate running sum that expand the sequence to the right side (only modify the ending index)

if the running sum becomes lower than the current maximum, we make our sequence start at that point