Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

Say you have an array for which the i^th 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).

» Solve this problem

Idea: The best choice could be the max of: do nothing / one more transaction based on the previous result on day j where j < i and at most one transaction was made before day j

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = prices.size();
        if (n <= 1) return 0;
        
        int minp = prices[0];
        int *dp = new int[n];
        int *dp1 = new int[n]; //max profit with one or less transaction
        
        memset(dp, 0, n*sizeof(int));
        memset(dp1, 0, n*sizeof(int));
        
        for (int i = 1; i < n; i++) {
            if (prices[i] < minp) minp = prices[i];
            dp1[i] = max(dp1[i-1], prices[i] - minp);
            if (prices[i] <= prices[i-1]) {
                dp[i] = dp[i-1];
                continue;
            }
            for (int j = 0; j < i; j++) {
                dp[i] = max(dp[i], dp1[j] + prices[i] - prices[j]);
            }
            dp[i] = max(dp[i], dp[i-1]);
        }
        
        return dp[n-1];
    }
};