Analysis of the algorithm "Search for the maximum amount of subsequent elements"

Question

If possible, I would like someone to give an analytical explanation of the algorithm.

For example, given the sequence

-2, 4, -1, 3, 5, -6, 1, 2 

the maximum amount of subsequence would be

 4 + -1 + 3 + 5 = 11 

This algorithm I'm reading is an algorithm like divide and cconquer.

An algorithm is O (nlogn) complexity.

Actually, I am looking for an example of all the steps that this algorithm creates. The above sequence can be used as an example.

Answer 1

The idea is to split your sequence in half, find the answers for both halves, and then use this to find the answer for the whole sequence.

Suppose you have the sequence [left, right] . Let m = (left + right) / 2 . Now the maximum sum of a subsequence ( MSS ) [left, right] is equal to either MSS(left, m) , MSS(m + 1, right) or a sequence that starts in [left, m] and ends somewhere in [m + 1, right] .

pseudo code:

 MSS(left, right) if left = right then return sequence[left] m = (left + right) / 2 leftMSS = MSS(left, m) rightMSS = MSS(m + 1, right) maxLeft = -inf // find the maximum sum subsequence that ends with m and starts with at least left cur = 0 i = m while i >= left do cur += sequence[i] if cur > maxLeft maxLeft = cur maxRight = -inf // find the maximum sum subsequence that starts with m + 1 and ends with at most right cur = 0 i = m + 1 while i <= right cur += sequence[i] if cur > maxRight maxRight = cur return max(leftMSS, rightMSS, maxLeft + maxRight) 

This is O(n log n) , because the recursion of three has a height of O(log n) and at each level of the tree we execute O(n) .

Here's how it will work on -2, 4, -1, 3, 5, -6, 1, 2 :

  0 1 2 3 4 5 6 7 -2 4 -1 3 5 -6 1 2 MSS(0, 7) = 11 / \ MSS(0, 3) = 6 MSS(4, 7) = 5 ------ / \ | \ MSS(0, 1) = 4 MSS(2, 3) = 3 MSS(4, 5) = 5 NSS(6, 7) = 3 / \ / \ MSS(0, 0) = -2 MSS(1, 1) = 4 MSS(2, 2) = -1 MSS(3, 3) = 3 

Of interest is the calculation of MSS(0, 3) and MSS(0, 7) , since they do not just accept the maximum of their children. For MSS(0, 3) we try to make the largest possible amount by adding sequential elements, starting from the middle of the interval (1) and going to the left. This maximum is 4 . Then we do the same thing, starting from the middle of the interval + 1 and go right. This maximum is 2 . Adding them together, we get the maximum sum of the subsequence with the sum of 6 , which is greater than the maximum subsequence of the two child intervals, so we take it instead.

The rationale is similar for MSS(0, 7) .

Answer 2

This can be done O (n) times using the Kadane algorithm . I wrote my own version and an analysis of its complexity , if you're interested. The idea is to use dynamic programming to gradually improve the solution until the optimal subsequence is found.