Best Time to Buy and Sell Stock III
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.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution:
Similar to Trapping Rain Water problem. First check from left to right to find the maximum profit between the start to the i-th day.
Then check from right to left to find the maximum profit between the i-th day to the end.
Add two arrays and find the maximum profit.
The following code passes LeetCode Online Large Judge.
Comments
Post a Comment