Clean Java DP O(nk) solution with O(k) space


  • 15
    L

    Extend small_box's idea for "Best Time to Buy and Sell Stock III" to general case.
    https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1

    public int maxProfit(int k, int[] prices) {
        if(k>=prices.length/2){
            int maxProfit = 0;
            for(int i=1; i<prices.length; i++){
                if(prices[i]>prices[i-1]) maxProfit += prices[i]-prices[i-1];
            }
            return maxProfit;
        }
        
        int[] maxProfit = new int[k+1];
        int[] lowPrice = new int[k+1];
        for(int i=0; i<lowPrice.length; i++) lowPrice[i]=Integer.MAX_VALUE;
        for(int p : prices){
            for(int i=k; i>=1; i--){
                maxProfit[i] = Math.max(maxProfit[i],p-lowPrice[i]);
                lowPrice[i] = Math.min(lowPrice[i],p-maxProfit[i-1]);
            }
        }
        return maxProfit[k];
    }
    

Log in to reply
 

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