A Java Solution. No need to allocate that much space.


  • 0
    C

    This is similar as Problem 123
    Since we made some money at last transaction.
    The price we buy this time should minus the price we sale last time.
    buy[i] = Math.min(buy[i], price - sale[i - 1]);

    public int maxProfit(int k, int[] prices) {
    		if (k >= prices.length / 2) return quickSolve(prices);
    		
            int[] buy = new int[k + 1], sale = new int[k + 1];
            
            Arrays.fill(buy, Integer.MAX_VALUE);
            
            for(int price : prices){
            	for(int i = k; i >= 1; i--){
            		sale[i] = Math.max(sale[i], price - buy[i]);
            		buy[i] = Math.min(buy[i], price - sale[i - 1]);
            	}
            }
            
            return sale[k];
        }
    	
    	private int quickSolve(int[] prices) {
            int profit = 0;
            
            for (int i = 1; i < prices.length; i++){
                if (prices[i] > prices[i - 1]){
                	profit += prices[i] - prices[i - 1];
                }
            }
            
            return profit;
        }
    

Log in to reply
 

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