The 3-lines solution is misleading solution, because only when we hold a share can you sell a share. My DP solution by C++


  • -1
    D

    Theoretically, we just need to sum over all forward differences which are positive. But, in this question, we are not allowed to sell the share continuously, because only when we hold a share can you sell a share. So, the correct solution is dynamic programming(DP).

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        vector<int> dp(n,0);
        int minPrice = prices[0],res = 0;
        for (int i = 1;i < n;++i) {
            minPrice = min(minPrice,prices[i]);
            if (prices[i]-minPrice>=dp[i-1]) dp[i] = prices[i]-minPrice;
            else {
                minPrice = prices[i];
                res += dp[i-1];
            }
        }
        
        return res+dp[n-1];
    }

  • 0
    B

    I agree with you, cause we can't transcate twice at the same day


  • 0

    @DjangoBUAA Maybe it's indeed "misleading" (at least you), but it's correct, so I find your post misleading. Selling and buying on the same day is equivalent to doing neither, and that is allowed.

    Edit: Oh wait, I just read your text again, and I now think you're mistaken in a different way. Maybe show a small example case and what you think the solution you're referring to is doing with it.


Log in to reply
 

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