Concise JAVA solution based on DP


  • 1
      public int maxProfit(int k, int[] prices) {
    	  if (prices==null) return 0;
    	  int len = prices.length;
          // One transaction takes two steps: buy and sell. So k * 2 >= len means we can complete unlimited transactions.
    	  if (k * 2 >= len) {
    		  int max = 0;
    		  for (int i = 1; i < prices.length; i++)
    			 if (prices[i] - prices[i - 1] > 0)
    				 max += prices[i] - prices[i - 1];
    		  return max;
    	  }
    	  
         // max[i][j]: Maximum profit for i prices with j transactions	
    	  int max[][] = new int[len][k+1]; 	  
    	  for (int j = 1; j <= k; j++) {
              // maxLeftMoneyWithUnsoldStock : Maximum left money in hand, with the stock unsold.
    		  int maxLeftMoneyWithUnsoldStock = -prices[0]; 
    		  for (int i = 1; i < len; i++) {
                  // 1) max[i-1][j]: Already finished j transactions in i - 1 time; 
                  // 2) maxLeftMoneyWithUnsoldStock + prices[i] : sell the stock this time.
    			  max[i][j] = Math.max(max[i-1][j], maxLeftMoneyWithUnsoldStock + prices[i]); 	
    			  maxLeftMoneyWithUnsoldStock = Math.max(maxLeftMoneyWithUnsoldStock, max[i-1][j-1] - prices[i]); 
    		  }
    	  }	  
    	  return max[len-1][k];
      }

Log in to reply
 

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