# 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.