首页>itarticle>leetcode 188 best time to buy and sell stock iv
leetcode 188 best time to buy and sell stock iv
admin11月 14, 20200
Say you have an array for which the ithelement is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most ktransactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
1 2 3
Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
1 2 3 4
Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
publicclass{ publicintmaxProfit(int k, int[] prices){ if (k >= prices.length / 2) { 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; }
// while k < len(price)/ 2, we need using dp solutions to solve the question. // profit[i][j], means the max profit we could get when we have i transactions up to the j-th price; int profit[][] = newint[k+1][prices.length];
for (int i=1; i<=k; i++) { int max = -prices[0]; for (int j=0; j<prices.length; j++) { profit[i][j] = Math.max(profit[i][j-1], prices[j] + max); max = Math.max(max, profit[i-1][j-1]-prices[j]); } } return profit[k][prices.length-1]; } }
近期评论