leetcode/code/lc188.java at master · mJackie/leetcode · GitHub

37 lines (36 loc) · 1.45 KB

package code;

* 188. Best Time to Buy and Sell Stock IV

* 题意：买卖股票最大利润，可以买卖k次

* 难度：Hard

* 分类：Dynamic Programming

* 思路：二维dp, dp[i][j] 表示i次交易，在数组prices[0~j]上的最大利润

* dp[i][j] = Max( dp[i][j-1], dp[i-1][jj]+prices[j]-prices[jj] ) { jj in range of [0, j-1] }

* = Max( dp[i][j-1], prices[j]+ max(dp[i-1][jj]-prices[jj]) ) 转化为这一步，少了一层循环

* dp[0][j] = 0; dp[i][0] = 0;

* Tips：lc121, lc309, lc188, lc123, lc714

public class lc188 {

public int maxProfit(int k, int[] prices) {

if(prices.length==0) return 0;

int n = prices.length;

//if k >= n/2, then you can make maximum number of transactions.

if (k >= n/2) {

int maxPro = 0;

for (int i = 1; i < n; i++) {

if (prices[i] > prices[i-1])

maxPro += prices[i] - prices[i-1];

}

return maxPro;

}

int[][] dp = new int[k+1][prices.length];

for (int i = 1; i <= k ; i++) {

int localMax = -prices[0];

for (int j = 1; j < prices.length ; j++) { //jj的计算和这一维合并，总的复杂度是二次方而不是三次

dp[i][j] = Math.max(dp[i][j-1], prices[j]+localMax);

localMax = Math.max(localMax, dp[i-1][j]-prices[j]);

}

return dp[k][prices.length-1];

}

Expand file tree