原題網(wǎng)址：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Say you have an array for which the?ith?element is the price of a given stock on day?i.

Design an algorithm to find the maximum profit. You may complete at most?k?transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

思路：定義兩個二維變量，

last[j][i]，表示恰好在第j日完成第i次交易的最大收益。

total[j][i]，表示在第j日之前（含）完成i次交易的最大收益。

那么如何遞歸或者遞推計算兩個變量的值呢？我們先考慮total變量，第j日之前完成i次交易，可以分為兩種情況，第一種情況是最后一日不作任何交易，第二種是最后一日完成第i次交易，則total[j][i] = max(total[j-1][i], last[j][i])，這個比較容易理解。如何計算last呢？我們可以按照倒數(shù)第二日的交易情況進(jìn)行分類，分為倒數(shù)第二日完成第i次交易，以及倒數(shù)第二日不做任何交易。對于前者，我們可以觀察如果倒數(shù)第二日的第i次交易推遲到第i日的獲利情況；對于后者，我們可以觀察倒數(shù)第二日買入，最后一日（第j日）賣出的情況，即：last[j][i] = max(0, last[j-1][i] + prices[j] - prices[j-1], total[j-1][i-1] + prices[j] - prices[j-1])。為什么會有0呢？因為我們的交易至少不能虧錢，如果一定要有交易的話，我們當(dāng)天買入、當(dāng)天賣出，至少是可以不虧的。但會不會有其他情況呢？例如最后一次交易有沒有可能是倒數(shù)第三天買入，最后一天賣出？分析下面六種情況，可以知道公式是正確的。

數(shù)據(jù)流演示：

方法一：動態(tài)規(guī)劃。

public class Solution {private int max(int[] prices) {int max = 0;for(int i=1; i<prices.length; i++) {max += Math.max(0, prices[i] - prices[i-1]);}return max;}public int maxProfit(int k, int[] prices) {if (prices == null || prices.length < 2) return 0;int n = prices.length;if (k >= n/2) return max(prices);int[][] last = new int[n][k+1];int[][] total = new int[n][k+1];for(int t = 1; t <= k; t ++) {for(int d = 1; d < n; d ++) {last[d][t] = Math.max(last[d-1][t] + prices[d] - prices[d-1], total[d-1][t-1] + Math.max(0, prices[d] - prices[d-1]));total[d][t] = Math.max(total[d-1][t], last[d][t]);}}return total[n-1][k];} }
方法二：在方法一的基礎(chǔ)上，優(yōu)化內(nèi)存分配。

public class Solution {private int max(int[] prices) {int max = 0;for(int i=1; i<prices.length; i++) {int p = prices[i] - prices[i-1];if (p>0) max += p;}return max;}public int maxProfit(int k, int[] prices) {if (prices == null || prices.length < 2) return 0;int n = prices.length;if (k >= n/2) return max(prices);int[] last = new int[n];int[] total = new int[n];int[] prevTotal = new int[n];for(int t = 1; t <= k; t ++) {int[] tempTotal = prevTotal;prevTotal = total;total = tempTotal;for(int d = 1; d < n; d ++) {last[d] = Math.max(last[d-1] + prices[d] - prices[d-1], prevTotal[d-1] + Math.max(0, prices[d] - prices[d-1]));total[d] = Math.max(total[d-1], last[d]);}}return total[n-1];} }

這里有個訣竅，其實臨時變量prevTotal可以省略：

public class Solution {private int max(int[] prices) {int max = 0;for(int i=1; i<prices.length; i++) {int p = prices[i] - prices[i-1];if (p>0) max += p;}return max;}public int maxProfit(int k, int[] prices) {if (prices == null || prices.length < 2) return 0;int n = prices.length;if (k >= n/2) return max(prices);int[] last = new int[n];int[] total = new int[n];for(int t = 1; t <= k; t ++) {for(int d = 1; d < n; d ++) {last[d] = Math.max(last[d-1] + prices[d] - prices[d-1], total[d-1] + Math.max(0, prices[d] - prices[d-1]));}for(int d = 1; d < n; d ++) {total[d] = Math.max(total[d-1], last[d]);}}return total[n-1];} }

方法三：同樣是動態(tài)規(guī)劃，但是用日期作為外層循環(huán)，把交易作為內(nèi)層循環(huán)：

public class Solution {private int max(int[] prices) {int max = 0;for(int i=1; i<prices.length; i++) {max += Math.max(0, prices[i] - prices[i-1]);}return max;}public int maxProfit(int k, int[] prices) {if (prices == null || prices.length < 2) return 0;int n = prices.length;if (k >= n/2) return max(prices);int[][] last = new int[k+1][n];int[][] total = new int[k+1][n];for(int d = 1; d < n; d ++) {int diff = prices[d] - prices[d-1];for(int t = 1; t <= k; t ++) {last[t][d] = Math.max(0, last[t][d-1] + diff);last[t][d] = Math.max(last[t][d], total[t-1][d-1] + Math.max(0, diff));total[t][d] = Math.max(total[t][d-1], last[t][d]);}}return total[k][n-1];} }
方法四：在方法三的基礎(chǔ)上優(yōu)化內(nèi)存，這里有個訣竅，只需要讓t從k到1倒過來，就可以節(jié)省上一層循環(huán)的內(nèi)存空間！

public class Solution {private int max(int[] prices) {int max = 0;for(int i=1; i<prices.length; i++) {max += Math.max(0, prices[i] - prices[i-1]);}return max;}public int maxProfit(int k, int[] prices) {if (prices == null || prices.length < 2) return 0;int n = prices.length;if (k >= n/2) return max(prices);int[] last = new int[k+1];int[] total = new int[k+1];for(int d = 1; d < n; d ++) {int diff = prices[d] - prices[d-1];for(int t = k; t >= 1; t --) {last[t] = Math.max(0, last[t] + diff);last[t] = Math.max(last[t], total[t-1] + Math.max(0, diff));total[t] = Math.max(total[t], last[t]);}}return total[k];} }
方法五：采用最大堆來對波段的盈利進(jìn)行排序，使用棧來保持未能確定操作方式的波段。我沒有想出來，參考網(wǎng)上的： https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack

public class Solution {private int max(int[] prices) {int max = 0;for(int i=1; i<prices.length; i++) {int p = prices[i] - prices[i-1];if (p>0) max += p;}return max;}public int maxProfit(int k, int[] prices) {if (prices == null || prices.length < 2) return 0;int n = prices.length;if (k >= n/2) return max(prices);PriorityQueue<Integer> profits = new PriorityQueue<>(Collections.reverseOrder());Stack<int[]> waves = new Stack<>();int v = 0, p = 0;while (p < n) {for(v = p; v < n - 1 && prices[v] >= prices[v+1]; v ++);for(p = v + 1; p < n && prices[p] >= prices[p-1]; p ++);while (!waves.isEmpty()) {int[] wave = waves.peek();if (prices[v] >= prices[wave[0]]) break;profits.offer(prices[wave[1]-1]-prices[wave[0]]);waves.pop();}while (!waves.isEmpty()) {int[] wave = waves.peek();if (prices[p-1] < prices[wave[1]-1]) break;profits.offer(prices[wave[1]-1]-prices[v]);v = wave[0];waves.pop();}waves.push(new int[] {v, p});}while (!waves.isEmpty()) {int[] wave = waves.pop();profits.offer(prices[wave[1]-1]-prices[wave[0]]);}int max = 0;for(int i = 0; i < k && !profits.isEmpty(); i ++) {max += profits.poll();}return max;} }

方法六：神奇的方法，網(wǎng)上看來的，一開始沒有弄明白。

public class Solution {public int maxProfit(int k, int[] prices) {if (k < 1 || prices == null || prices.length < 2) return 0;if (k >= prices.length/2) {int max = 0;for(int i=1; i<prices.length; i++) max += Math.max(0, prices[i]-prices[i-1]);return max;}int[] buy = new int[k];int[] sell = new int[k];Arrays.fill(buy, Integer.MIN_VALUE);for(int i=0; i<prices.length; i++) {for(int j=0; j<k; j++) {buy[j] = Math.max(buy[j], j==0?-prices[i]:sell[j-1]-prices[i]);sell[j] = Math.max(sell[j], buy[j]+prices[i]);}}return sell[k-1];} }

然后分析上面代碼，發(fā)現(xiàn)和下面是等價的，看起來就比較像動態(tài)規(guī)劃了。

public class Solution {public int maxProfit(int k, int[] prices) {if (k <= 0 || prices.length < 2) return 0;int n = prices.length;if (k >= n / 2) {int max = 0;for(int i = 1; i < n; i++) {max += Math.max(0, prices[i] - prices[i - 1]);}return max;}int[][] buy = new int[prices.length+1][k+1]; int[][] sell = new int[prices.length+1][k+1]; Arrays.fill(buy[0], Integer.MIN_VALUE); for(int i=1; i<=prices.length; i++) { for(int j=1; j<=k; j++) { buy[i][j] = Math.max(buy[i-1][j], sell[i][j-1]-prices[i-1]);sell[i][j] = Math.max(sell[i-1][j], buy[i][j]+prices[i-1]);} } return sell[prices.length][k]; } }神奇的是，上面的i和j循環(huán)可以互換，不影響結(jié)果！

看數(shù)據(jù)流，可以幫助理解這個算法：

總結(jié)

以上是生活随笔為你收集整理的LeetCode 188. Best Time to Buy and Sell Stock IV（股票买卖）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。