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).

Analyse: Consider a dp function s.t. dp[i] = max_profit[0,....i-1] + max_profit[i,...n]. Then the problem is transferred to compute the max dp[i]. To get max profit of a interval, we can use the code in here. You have to pay special attention that the LEFT AND RIGHT PART of a indexed number are COMPLETED SEPERATED. 

1. Time Exceeded.

This is because when calling the dp function, we repeat the computation for a lot of times.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1) return 0;
        
        int result = 0;
        for(int i = 0; i < prices.size(); i++){
            result = max(result, dp(prices, 0, i) + dp(prices, i, prices.size()));
        }
        return result;
    }
    int dp(vector<int>& prices, int start, int end) {
        if(start == end) return 0;
        
        int result = 0, pre = 0;
        int lowest = prices[start];
        for(int i = start + 1; i < end; i++){
            result = max(pre, prices[i] - lowest);
            lowest = min(lowest, prices[i]);
            pre = result;
        }
       return result;
    }
};

2. To solve the above problem, we can store the computed information in an array, for example, a[] store the computed information in the left part and b[] store the computed information in the right part. 

    Runtime: 12ms.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1) return 0;
        
        const int n = prices.size();
        int left[n] = {0}, right[n] = {0};
        dp(prices, left, right);
        int result = 0;
        for(int i = 0; i < prices.size(); i++){
            result = max(result, left[i] + right[i]);
        }
        return result;
    }
    void dp(vector<int>& prices, int left[], int right[]) {
        int lowest = prices[0];
        for(int i = 1; i < prices.size(); i++){//to initial the left part of the indexed number
            left[i] = max(left[i - 1], prices[i] - lowest);
            lowest = min(lowest, prices[i]);
        }
        
        int highest = prices[prices.size() - 1];
        right[prices.size() - 1] = 0;
        for(int j = prices.size() - 2; j >= 0; j--){
            right[j] = max(right[j + 1], highest - prices[j]);
            highest = max(highest, prices[j]);
        }
    }
};