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

  • 15

    Extend small_box's idea for "Best Time to Buy and Sell Stock III" to general case.

    public int maxProfit(int k, int[] prices) {
            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.