Recitation 001


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)

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

  1. 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
  2. we calculate running sum that expand the sequence to the right side (only modify the ending index)
  3. if the running sum becomes lower than the current maximum, we make our sequence start at that point

Table of Content