Share the joy
This is from leetcode: link. Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions.
The solution is to maintain 2 array, maxLeft[], maxRight[]. maxLeft[i] maintains the max profit from price[0],…,price[i] by one transaction. maxRight[i] maintains from price[i],…,price[length-1] by one transaction. Then we find i where we can get max{maxLeft[i]+maxRight[i]}.
Check my code on github: link