Best Time to Buy and Sell Stock III [LeetCode]

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: DP, caculate max profit both forward and backward, then return the max sum of them.

 1     int maxProfit(vector<int> &prices) {
 2         if(prices.size() <= 1)
 3             return 0;
 4             
 5         vector<int> max_forward;
 6         int lowest = prices[0];
 7         int max_profit = 0;
 8         max_forward.push_back(0);
 9         for(int i = 1; i < prices.size(); i ++ ){
10             int profit = prices[i] - lowest;
11             if(profit > max_profit)
12                 max_profit = profit;
13             
14             max_forward.push_back(max_profit);
15             lowest = min(prices[i], lowest);
16         }
17         
18         int result = max_forward[max_forward.size() - 1];
19         vector<int> max_backward;
20         int largest = prices[prices.size() - 1];
21         max_profit = 0;
22         for(int i = prices.size() - 2; i >= 0; i --) {
23             int profit = largest - prices[i];
24             max_profit = max(profit, max_profit);
25             
26             result = max(result, max_profit + max_forward[i]);
27             
28             largest = max(largest, prices[i]);
29         }
30         return result;
31     }