2 k-length arrays DP solution


  • 0
    H

    Inspired by a solution in Best Time to Buy and Sell Stock III. The solution of this problem can only be got from sell k times, buy k times, sell k-1 times, buy k-1 times, ..., sell 1st time, buy 1st time. So we just need to iterate those possibilities.

    public int maxProfit(int k, int[] prices) {
            if (prices == null || k < 1) {
                return 0;
            }
            
            if (prices.length <= k) { // just do greedy
                return helper(prices);
            }
            
            final int[] sells = new int[k];
            final int[] holds = new int[k];
    
            for (int i = 0; i < holds.length; i++) {
                holds[i] = Integer.MIN_VALUE;
            }
            
            for (int i = 0; i < prices.length; i++) {
                for (int j = k - 1; j >= 0; j--) {
                    sells[j] = Math.max(sells[j], holds[j] + prices[i]);
                    int sell = j == 0 ? 0 : sells[j - 1];
                    holds[j] = Math.max(holds[j], sell - prices[i]);
                }
            }
            return sells[k - 1];
        }
        
        
        private int helper(int[] prices) {
            int max = 0;
            for (int i = 0; i < prices.length - 1; i++) {
                if (prices[i] < prices[i + 1]) {
                    max += prices[i + 1] - prices[i];
                } 
            }
            return max;
        }
    

Log in to reply
 

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