Clean C++ 6 line DP Solution. O(n) time, O(1) space

  • 1

    Define dp[i] as maximum profit till time i. Thus,

    dp[i] = max(dp[i-1],//no transaction on ith day
                dp[j-1] + a[i]-a[j])//transaction on ith day with maximum revenue.

    We can save maximum value of dp[j-1]-a[j] as a single variable in dpDiffMax and dpAns as dp[i].

    int maxProfit(vector<int>& prices, int fee) {
            int dpDiffMax = -prices[0], dpAns = 0;
            for(int i = 0; i < prices.size(); i++) {
                int temp = dpAns;
                dpAns = max(dpAns, prices[i] + dpDiffMax - fee);
                dpDiffMax = max(dpDiffMax, temp - prices[i]);
            return dpAns;

Log in to reply

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