DP #28. Buy Sell Stock III - mbhushan/dynpro GitHub Wiki

(28). Buy 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:
A transaction is a buy & a sell. You may not engage in multiple transactions 
at the same time (ie, you must sell the stock before you buy again).

We use left[i] to track the maximum profit for transactions before i, and use right[i] to track the maximum profit for transactions after i. You can use the following example to understand the Java solution:

Prices: 1 4 5 7 6 3 2 9
left = [0, 3, 4, 6, 6, 6, 6, 8]
right= [8, 7, 7, 7, 7, 7, 7, 0]
The maximum profit = 13

Buy Sell - 2 Transaction

• Time Complexity: O(n^2)
• Space Complexity: O(n)