給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。

注意:?你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例?1:

輸入: [2,4,1], k = 2
輸出: 2
解釋: 在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。
示例 2:

輸入: [3,2,6,5,0,3], k = 2
輸出: 7
解釋: 在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。
?? ? 隨后，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。

思路：同之前的允許交易兩次的題類似，只不過把交易次數k變大

但需要注意，這道題定義dp[length][k][2]，會超出內存限制，所有應該是k過大，k最大不過是數組的一半，他的交易數量不可能超過這個值，所以當交易次數超過數組長度一半時，調用之前的方法maxProfit1，k視為無限大，可以忽略，定義dp[length][2]

之前交易兩次的鏈接：https://mp.csdn.net/postedit/102924843

提交的代碼：

class Solution {
? ? public static int maxProfit1(int[] prices) {
?? ?int sum=0;
? ? ? ? for(int i=1;i<prices.length;i++)
? ? ? ? {
? ? ? ? ?? ?if(prices[i]-prices[i-1]>0)
? ? ? ? ?? ?{
? ? ? ? ?? ??? ?sum+=prices[i]-prices[i-1];
? ? ? ? ?? ?}
? ? ? ? }
? ? ? ? return sum;
? ? }
? ? public int maxProfit(int k, int[] prices) {
? ? ? ? if(k>prices.length/2)
? ? ? ? {
? ? ? ? ? ? return maxProfit1(prices);
? ? ? ? }
? ? ? ? if(prices.length==0||k==0)
? ? {
? ? ? ? return 0;
? ? }
?? ?int dp[][][] = new int[prices.length][k+1][2];
?? ?dp[0][0][0] = 0;
? ? dp[0][0][1] = Integer.MIN_VALUE >> 1;
? ? for(int i=1;i<=k;i++)
? ? {
? ? ?? ?dp[0][i][0]=0;
? ? ?? ?dp[0][i][1]=-prices[0];
? ? }
?? ?dp[0][1][1] = -prices[0];
?? ?for(int i=1;i<prices.length;i++)
?? ?{
?? ??? ?for(int j = 1;j<=k;j++)
?? ??? ?{
?? ??? ??? ?dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
?? ??? ??? ?dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);?? ?
?? ??? ?}
?? ?}
?? ?int max = dp[prices.length-1][0][0];
?? ?for(int i=1;i<=k;i++)
?? ?{
?? ??? ?if(dp[prices.length-1][k][0]>max)
?? ??? ?{
?? ??? ??? ?max = dp[prices.length-1][k][0];
?? ??? ?}
?? ?}
?? ?return max;

? ? }
}

總結

以上是生活随笔為你收集整理的Leetcode--188. 买卖股票的最佳时机Ⅳ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。