Two states DP C++ code


  • 6
    M

    f(i, 0) is the max profit with one stock in hand. f(i, 1) is the max profit with no stock in hand.

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            vector<vector<int>> f;
            int n = prices.size();
            if (n <= 1) {
                return 0;
            } else if (n == 2) {
                return max(0, prices[1] - prices[0]);
            }
        
            f = vector<vector<int>>(n, vector<int>(2));
            
            f[0][0] = -prices[0];
            f[0][1] = 0;
            f[1][0] = max(-prices[0], -prices[1]);
            f[1][1] = max(0, prices[1] - prices[0]);
            
            for (int i = 2; i < n; i++) {
                f[i][0] = max(f[i - 1][0], f[i - 2][1] - prices[i]);
                f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);
            }
            
            return f[n - 1][1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.