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.
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)
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
0
, initialize a current maximum to 0
and starting and ending index of how to get the maximum sumTable of Content