Fast & Clean DP Solution in Java

  • 2
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int[] c = new int[prices.length];
        int[] s = new int[prices.length];
        c[0] = 0;
        c[1] = 0;
        s[1] = prices[1] - prices[0];
        for(int i = 2; i < prices.length; i++){
            c[i] = Math.max(s[i-1], c[i-1]);
            // If current state is cool down, 
            s[i] = prices[i] - prices[i-1] + Math.max(c[i-2], s[i-1]); 
            // If current state is sold, assume it was sold at [i-1]
        return Math.max(c[prices.length-1], s[prices.length-1]);

  • 0
      s[i] = prices[i] - prices[i-1] + Math.max(c[i-2], s[i-1]);

    May I understand it this way? c[i-2] equals buy[i-1], means buy on i - 1 and sell it on i; s[i-1] is selling on i-1, but actually you should not sell it so early, you should sell it on today (i) so you add profit difference (i to i -1) back? But it seems not right..

  • 0

    s[i-1] means you did not buy it on i-1. You buy it sometime earlier than i-1.

Log in to reply

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