O(n*k) time O(k) space Java DP Solution, Generalized from Best Time to Buy and Sell Stock 3


  • 1
    public int maxProfit(int k, int[] prices) {
        if (k <= 0) {
            return 0;
        }
        if (k >= prices.length / 2) {
            return maxProfit(prices);
        }
        int[] buy = new int[k];
        Arrays.fill(buy, Integer.MIN_VALUE);
        int[] sell = new int[k];
        for (int i = 0; i < prices.length; i++) {
            for (int j = 0; j < k; j++) {
                if (j == 0) {
                    buy[j] = Math.max(buy[j], -prices[i]);
                    sell[j] = Math.max(sell[j], buy[j] + prices[i]);
                } else {
                    buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
                    sell[j] = Math.max(sell[j], buy[j] + prices[i]);
                }
            }
        }
        return sell[k - 1];
    }
    
    private int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            max += (prices[i] - prices[i - 1] > 0) ? prices[i] - prices[i - 1] : 0;
        }
        return max;
    }

Log in to reply
 

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