Best Time to Buy and Sell Stock III

Desicription

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProfit(vector<int>& prices) {
int hold1 = INT_MIN;
int hold2 = INT_MIN;
int release1 = 0;
int release2 = 0;
for(int price : prices) {
hold1 = max(hold1, -price);
release1 = max(release1, hold1 + price);
hold2 = max(hold2, release1 - price);
release2 = max(release2, hold2 + price);
}
return release2;
}
};