Recitation 001

MCSS

Brute Force Algorithm: potentially search for all possible solution

Subsequence: b of a sequence a is a sequence that can be derived from a by deleting elements of a without changing the order of remaining elements.

Contiguous Subsequence: subsequence that is only deleted from the master sequence from front or/and end.

$MCSS(a) = \max \left(0, \max \{ \sum_{k = 1}^i a[k] : 0 \leq i, j < |a|\} \right)$

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

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

Table of Content