O(nk)-time O(k)-space easy to understand 6ms Java solution


  • 0
    I
      public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (len <= 1 || k == 0) {
            return 0;
        }
        if (k >= len / 2) {
            int max = 0;
            for (int i = 1; i < len; i++) {
                if (prices[i] > prices[i - 1]) max += prices[i] - prices[i - 1];
            }
            return max;
        }
        // Suppose state is defined as f(i,k) where i is the time and k is the transactions remained.
        // The problem is how do we know if we are allowed to perform a sell operation or not at a specific state.
        // Because with f(i,k), we can't jump into f(i+1 , k-1) because k, representing transactions, involves two operations happened at different time(different i), it doesn't clearly shows the holding status.
        
        // One solution is to expand the state to f(i,k,h) where h could only be 0 or 1, shows whether we are holding a stock or not,
        // but this will complicate the calculations and may using extra time and space.
        
        // What we do is expanding k to 2*k to substitute h.
        // So totally, including both buying and selling, we are allowed to do 2*k operations.
        // To prevent selling before buying, we define even number of k as the time we hold nothing and can only buy a stock.
        // and therefore odd number of k as the time we are holding something in hand and can only sell. 
        // f(i , k) = if k%2==0 we can buy the stock or not
        //              buy        f(i+1 , k-1) - prices[i]
        //              do nothing f(i+1 , k) (k doesn't change so we still have the right to buy)
        //            
        //            if k%2==1 we are holding a stock right now so only sell it or do nothing
        //              sell       f(i+1 , k-1) + prices[i]
        //              do nothing f(i+1 , k) (k doesn't change so we are still holding a stock)
        
    
        // O(nk) Space without optimization
        //
        // int[][] dp= new int[len+1][k*2+2];
        // for(int i = len-1; i>=0; i--){
        //     for(int j = k*2; j>0; j--){
        //         dp[i][j] = dp[i+1][j];
        //         if(j%2==1){
        //             dp[i][j] = Math.max(dp[i][j], dp[i+1][j-1]+prices[i]);
        //         }else{
        //             dp[i][j] = Math.max(dp[i][j], dp[i+1][j-1]-prices[i]);
        //         }
        //     }
        // }
    
        // optimized in space, using O(k) instead of O(nk)
        int[] dp = new int[k * 2 + 2];
    
        for (int i = len - 1; i >= 0; i--) {
            for (int j = k * 2; j > 0; j--) {
                if (j % 2 == 1) {
                    dp[j] = Math.max(dp[j], dp[j - 1] + prices[i]);
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
                }
            }
        }
        return dp[k * 2];
    }

Log in to reply
 

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