问题描述
【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];
}
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr() (KMP超详细讲解,sunday解法等五种方法,java实现)
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)