Very simple explanation based basic math, (no state machine etc. ) O(N) DP code attached


  • 8
    C

    Define profit[i] - maximum profit can be made on day i following the cool down rule

    profit[i] = Max(prices[i]-prices[j] + profit[j-2]) for all j < i (1)

    • prices[i]-prices[j] buying on j and sell on i (1.1)
    • profit[j-2] accumulated profit from 0 to j-2 (1.2)

    Above calculation would lead to O(N^2) complexity, let's simplify using linearity

    profit[i] = Max(prices[i]) + Max(profit[j-2]-prices[j]) for all j<i (2)

    • Max( prices[i] ) = prices[i] is O(1) calculation
    • Max(profit[j-2]-prices[j]) for all j<i is O(1) calculation

    This is O(N), below is the code

    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n<=1) return 0;
        int[] dp = new int[n + 1];
        int max = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i + 1] = Math.max(dp[i], max + prices[i]);
            max = Math.max(dp[i - 1] - prices[i], max);
        }
    
        return dp[n];
    }
    

    Of course this post is here to illustrate the concept of DP, the space can further be optimized into O(1). Plus, if you read the other posts with state machines and buy,sell,cool down states, it's all reduces into this format. The only difference if how you explain the variables you define in each case.


  • 3
    W

    I think the formula should be

    profit[i] = Max(prices[i]-prices[j] + profit[j-2], profit[i-1]) for all j < i (1), it can be changed to:

    profit[i] = Max( prices[i] + max(profit[j-2]-prices[j]), profit[i-1] ) for all j<i (2)

    select profit[i-1] means sell stock on day i-1 and do nothing on day i

    prices[i]-prices[j] means buying on day j and sell on day i


Log in to reply
 

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