[Leetcode] Best Time to Buy and Sell Stock I II and III

Problem 

Say you have an array, where the ith element is the price of a given stock on day i.

design an algorithm to find the maximum profit. 

1. If you were only permitted to complete at most one transaction.

2. If you may complete as many transactions as you like

3. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e, you must sell the stock before you buy again).

Algorithms:

Problem 1 is the Maximum Subarray problem, which can be solved using Dynamic Programming. 

Let dp[i] = the maximum sum of subarray ending at i, and the recurrence is 

                    dp[i] =  max(0, A[i], dp[i-1] + A[i]), where i>0, and dp[0] = A[0].    

For ith element, we have three choices, 

1. add nothing, we gain 0 profit

2. add current element, we gain A[i]

3. add current element and previous maximum subarray's sum, we gain dp[i-1] + A[i],

we choose the max of above three options as the max sum end at i. The running time is O(n) and space complicity is O(n). 

We can reduce the space to constant. Observe that when we iterate the array, only the previous dp value is used. In addition, when dp[i-1] < 0, it must be smaller than A[i], therefore, we can safely set it to zero. We can maintain two variables, max_so_far and max_ending_here

For i = 0 to A.length - 1

   max_ending_here += max_ending_here + A[i]

   max_so_far = max(max_so_far, max_ending_here)

   max_ending_here = max(0,max_ending_here)

End

Problem 2 is the Maximum subsequence. Simply accumulate all the positive difference between A[i] and A[i-1].

Problem 3 
One obvious solution to problem 3 is to divide the array into two parts, say left and right. Then the problem is reduced to problem 1, finding the maximum subarray of left and right. The running time is O(n^2), since we divide at n positions (including not divide at all).

The above algorithm used divide, so we may devise a divide-and-conquer algorithm. If we divide the array into two halves, we need to find the solution in the left half and right half. In addition, a maximum subarray may cross the middle point. So, this solution is not easy to implement.

A O(n) solution exists. the original post can be found here.
Following the dynamic programming solution in problem 1, we can use two arrays E and S, where
      E[i] = maximum subarray sum ending at i
      S[i] = maximum subarray sum starting at i
Therefore, the maximum two transitions sum = max(E[i]+S[i])

The code should be refactored. 

Code