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.

Note: my code uses 2n extra spaces, which can be further reduced by n. The rightProfit array is not useful, we only need to store two temporary values.

Comments

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs