【LeetCode】Best|【LeetCode】Best Time to Buy and Sell Stock IV 动态规划dp解法(C++)
乍看此题有难度,实则解法有规律。
依然是动规来做,仔细分析后,我自然而然地联想到了求最大连续数之和的问题。最大连续数之和题意是给你一个无序数组,正数负数都有,让求出连续数字之和最大是多少。当然有很多种方法,复杂度比较低的还是dp解法。dp解法的关键是设置了两个变量来记录当前的一个状态,分别是最大连续数字和maxsofar和截止当前的最大连续数字maxtocur。举例来说,1,2,-4,7,-3,-2,6,对于这样一个数组,dp算法从左侧开始遍历,算法核心是公式maxsofar = max(maxsofar,maxtocur+cur).
此题与那个有相似之处,也有不同。这个题要求收益最大,也即在一个数组中找顺序数字的最大差值。当然此题还没那么简单,还要求可以最多交易k次。举例来说,如果给定一个数组是1,3,7,2,1,5 ,那么很明显最小值是1(注意虽然有两个数字1,但是第二个1是不可取的,因为我们为了获取最大收益要在7处卖掉,所以在那之前必须买入),最大值是7,所以只交易一次的最大收益即为6,同理交易两次最大收益是10(这应该很容易看出来吧?)
【【LeetCode】Best|【LeetCode】Best Time to Buy and Sell Stock IV 动态规划dp解法(C++)】类似最大连续和问题,我们需要变量来记录当前的一些状态信息,因为是k次交易,所以我们需要大小为k的数组记录每一次交易的信息,又因为一次交易包含买和卖两次操作,所以我们需要两个数组。分别命名为hold【】和sell【】。hold[i]表示第i次持有后的盈亏,也就是第i次买入后的状态,sell[i]表示第i次卖出后的盈亏状态。比如上个例子1,3,7,2,1,5.如果我们在第一天买入,那么hold[1]应该是-1,这里可能会问,为什么会是负数?那是因为我们买入了股票,钱已经花出去了,但我们还没有卖出,所以当前你手上是没有现金的,只有股票。
算法核心就是两句:
cur = prices[i];
hold[j] = max(hold[j],sell[j-1] - cur);
sell[j] = max(sell[j],hold[j] + cur);
在第i天第j次持有的盈亏最大是取两个的较大值,前一个表示继续持有,后一个表示在第j-1次卖出后,第i天又买入了。
在第i天第j次卖出的盈亏最大同上,也是比较两数取较大。
AC代码
class Solution {
public:
int maxProfit(int k, vector &prices) {
int len = prices.size();
if (len<2) return 0;
if (k>len/2){ // simple case
int ans = 0;
for (int i=1;
i
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗()
- 2019-02-13——今天谈梦想()
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境,人生还很长