锐客网

  1. 首页 > it技术 > >

求和|LeetCode 188. Best Time to Buy and Sell Stock IV（股票买卖）

动态规划贪心算法栈困难堆时间序列最值奇葩求和经典

原题网址：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呢？我们可以按照倒数第二日的交易情况进行分类，分为倒数第二日完成第i次交易，以及倒数第二日不做任何交易。对于前者，我们可以观察如果倒数第二日的第i次交易推迟到第i日的获利情况；对于后者，我们可以观察倒数第二日买入，最后一日（第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呢？因为我们的交易至少不能亏钱，如果一定要有交易的话，我们当天买入、当天卖出，至少是可以不亏的。但会不会有其他情况呢？例如最后一次交易有没有可能是倒数第三天买入，最后一天卖出？分析下面六种情况，可以知道公式是正确的。
求和|LeetCode 188. Best Time to Buy and Sell Stock IV（股票买卖）
文章图片


数据流演示：
【求和|LeetCode 188. Best Time to Buy and Sell Stock IV（股票买卖）】求和|LeetCode 188. Best Time to Buy and Sell Stock IV（股票买卖）
文章图片


方法一：动态规划。

public class Solution { private int max(int[] prices) { int max = 0; for(int i=1; i= 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]; } }


方法二：在方法一的基础上，优化内存分配。

public class Solution { private int max(int[] prices) { int max = 0; for(int i=1; i0) 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; i0) 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]; } }




方法三：同样是动态规划，但是用日期作为外层循环，把交易作为内层循环：

public class Solution { private int max(int[] prices) { int max = 0; for(int i=1; i= 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]; } }


方法四：在方法三的基础上优化内存，这里有个诀窍，只需要让t从k到1倒过来，就可以节省上一层循环的内存空间！

public class Solution { private int max(int[] prices) { int max = 0; for(int i=1; i= 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]; } }


方法五：采用最大堆来对波段的盈利进行排序，使用栈来保持未能确定操作方式的波段。我没有想出来，参考网上的： https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack
求和|LeetCode 188. Best Time to Buy and Sell Stock IV（股票买卖）
文章图片



public class Solution { private int max(int[] prices) { int max = 0; for(int i=1; i0) 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 profits = new PriorityQueue<>(Collections.reverseOrder()); Stack 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; } }


方法六：神奇的方法，网上看来的，一开始没有弄明白。

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

然后分析上面代码，发现和下面是等价的，看起来就比较像动态规划了。

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循环可以互换，不影响结果！
看数据流，可以帮助理解这个算法：
求和|LeetCode 188. Best Time to Buy and Sell Stock IV（股票买卖）
文章图片


    推荐阅读


    上一篇：基于bootstrap的提示弹窗实现

    下一篇：[windows Git] windows下cmd终端运行git