Java solution in O(n) time and O(K) space


  • 2

    Extended from Best Time to Buy and Sell Stock III.

        public int maxProfit(int k, int[] prices) {
            if(prices.length ==0){
                return 0;
            }
            
            if(k>=prices.length/2){
                int maxProfit = 0;
                for(int i=1; i<prices.length; i++){
                    maxProfit += Math.max(0, prices[i]-prices[i-1]);
                }
                return maxProfit;
            }
            
            int[] buy = new int[k+1];  //profit after buying at k-th transaction
            int[] sell = new int[k+1];  //profit at k-th transaction
            Arrays.fill(buy, Integer.MIN_VALUE);
            Arrays.fill(sell, 0);
            for(int price : prices){
                for(int i = 1; i<=k;i++){
                    buy[i] = Math.max(buy[i], sell[i-1]- price);
                    sell[i] = Math.max(sell[i], buy[i] + price);
                }
            }
            
            return sell[k];
        }
    

  • 1
    L

    It's not O(N) time but O(KN), your out loop is from 0 to prices.length, and your inner loop is from 1 to k.


  • 0

    Thank you for pointing this out.
    I thought K was constant, so I could remove it.


Log in to reply
 

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