LeetCode 188. Best Time to Buy and Sell Stock IV LeetCode

问题描述
【LeetCode 188. Best Time to Buy and Sell Stock IV】
文章图片

地址

问题分析

假设可以最多进行 k次交易，那么求能获得的最大利益
利用动态规划解题：首先明确两个状态的意义：
- local[i][j] : 第i天正好完成了j次交易的最大利益
- global[i][j] : 前i天完成了j次交易的最大利益
递归关系：
- local[j] = Math.max(local[j] + diff, global[j - 1] + Math.max(diff, 0));
- global[j] = Math.max(global[j], local[j]);
注意：
- 当 k >= len/2时，便等同于无限次交易 122. Best Time to Buy and Sell Stock II
- 当 k = 2 时，便是 123. Best Time to Buy and Sell Stock III

代码实现

原始动态规划

//local[i][j] : 第i天正好完成了j次交易的最大利益 //global[i][j] : 前i天完成了j次交易的最大利益 public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0 || k <= 0) { return 0; } int len = prices.length; int[][] local = new int[len][k + 1]; int[][] global = new int[len][k + 1]; for (int i = 1; i < len; ++i) { int diff = prices[i] - prices[i - 1]; //local[i][0] = 0; for (int j = 1; j < k + 1; ++j) { local[i][j] = Math.max(local[i - 1][j] + diff, global[i - 1][j - 1] + Math.max(diff, 0)); global[i][j] = Math.max(global[i - 1][j], local[i][j]); } } return global[len - 1][k]; }

动态规划优化空间

public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0 || k <= 0) { return 0; } int len = prices.length; if(k >= len / 2){ int sum = 0; for(int i = 1; i < prices.length; i++){ if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1]; } return sum; } int[] local = new int[k + 1]; int[] global = new int[k + 1]; for (int i = 1; i < len; ++i) { int diff = prices[i] - prices[i - 1]; //local[0] = 0; for (int j = k; j > 0; --j) { local[j] = Math.max(local[j] + diff, global[j - 1] + Math.max(diff, 0)); global[j] = Math.max(global[j], local[j]); } } return global[k]; }