Clean C++ DP with explanation


  • 0

    Explanation:

    Use one array to record the last bought stock with min price at day i, use another array to record the max profit at day i.

    The first solution we came up will be

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

    But you may noticed that we only concern the relationship between day i and day i - 1, therefore, we can simply use two integers to replace the two arrays, reduced space complexity to O(1).

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.empty()) return 0;
            int buy = prices[0], profit = 0;
            for(int i = 1; i < prices.size(); i++){
                buy = min(buy, prices[i]);
                profit = max(profit, prices[i] - buy);
            }
            return profit;
        }
    };
    

Log in to reply
 

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