你只能选择

返回你可以从这笔交易中获取的最大利润。

如果你不能获取任何利润返回

输入[7,1,5,3,6,4]

什么意思呢就比如第i天你卖出了股票好那第i1天如果你不买股票那应该是什么状态

如果还用“卖出”状态来表示那么就意味着第i1天仍然要卖出股票但实际上我们想表示的是这样一种状态“第i天卖出股票后如果第i1天不买那么第i天卖掉股票后的状态应该持续到第i1天”

因此使用买入和卖出来作为状态会漏掉一些状态还得单独为那些情况设定对应的状态进行表示

五步走

持有指的是我现在手头上有某只股票但不一定是今天买的有可能是之前某一天买的然后该状态延续到了现在

不持有指的是手头上已经没有股票了但不一定是今天卖的有可能是之前卖掉了然后该状态持续到了现在因为本题的股票只能买卖一次因此该状态会持续到最后一天

2、确定递推公式

然后如果是第i天不买入股票但状态仍是持有股票的话那么此时的状态是dp[i][0]

dp[i

综上取两者最大的情况那么持有股票时的递推公式为dp[i][0]

max(dp[i

如果是在第i天卖了股票那么此时除了状态需要转换为持有股票并且是i

1天持有因为第i天卖掉了就不持有了还需要加上第i天的股价price[i]作为收益即dp[i][1]

price[i]

也就是说如果当前的状态是不持有并且原因是那在第i天还没卖股票时此时的状态应该是dp[i][0]卖掉之后状态转变为dp[i][1]

显然不能用dp[i][1]

那么可以用price[i]表示第i天卖了股票因为得到了收益然后再用dp[i

1][0]表示我前一天确实有这个股票

综上取两者最大的情况那么不持有股票时的递推公式为dp[i][1]

max(dp[i

从两种情况下的递推公式来看dp[0][1]和dp[0][0]是递推的基础因此需要对其进行初始化

结合dp数组的定义dp[0][1]是第0天不持有股票所得到的最大收益那没有股票肯定是0啊而且我们初始资金也是0即dp[0][1]0

而dp[0][0]则是第0天持有股票所得到的最大收益因为是第0天所以不会存在前一天的情况

-price[i]

在这个题目中只需要求最终的最大利润而不需要知道具体是在哪个状态持有股票或不持有股票达到了最大利润因此直接返回dp[len

1][1]即可。

这是因为题目中规定最后一天必须卖出所有持有的股票而不是可以选择继续持有。

在遍历到最后一天后dp[len-1][0]表示最后一天持有股票的最大收益而dp[len-1][1]则表示最后一天不持有股票的最大收益。

我们只需要考虑最后一天的状态也就是持有股票和不持有股票的两种情况因为最后一天无法再进行任何交易了只有卖出股票才能获得收益。

因此我们只需要返回最后一天不持有股票的最大收益

dp[len-1][1]

设计一个算法来计算你所能获取的最大利润。

你可以尽可能地完成更多的交易多次买卖一支股票。

注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。

输入:

天接连购买股票之后再将它们卖出。

因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。

输入:

唯一不同的地方就是推导dp[i][0]和dp[i][0]的时候第i天买入股票的情况。

1持有股票dp[i][0]

如果是第i天买入的那么要用没有持有该股票时有的钱减去股票的售价即dp[i][0]

dp[i

如果是第i-1天买入的就还是和上一题一样状态延续到第i天即可即dp[i][0]

dp[i

如果是第i天卖掉的那就要用持有该股票时有的钱加上卖股票得的钱即dp[i][1]

dp[i

prices.size();//获取prices数组长度天数if(len

return

1][1];//最后一天要求把股票卖掉返回不持有股票的最大金钱数}

力扣题目链接(opens

注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。

输入prices

天接连购买股票之后再将它们卖出。

因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。

输入prices

与之前的两题最大的不同是之前一天只可以进行一次交易买卖总的交易次数也只有1次

五步走

回忆一下之前只能买卖一次时我们有两种情况即第i天持有或不持有股票

现在因为可以进行两次买卖所以第i天可能有的所有情况假设在第i天就进行两次交易就会有四种情况有四种

0、没有操作--dp[i][0]1、第i天第一次持有股票--dp[i][1]2、第i天第一次不持有股票--dp[i][2]3、第i天第二次持有股票--dp[i][3]4、第i天第二次不持有股票--dp[i][4]

2、确定递推公式

prices[i]用前一天状态下还剩的钱减去第i天买入股票的价格操作二第i天没有操作而是沿用前一天买入的状态即dp[i][1]

dp[i

操作二第i天没有操作沿用前一天卖出股票的状态即dp[i][2]

dp[i

在第0天第一次买入初始现金为0那么现在要扣除买股票的钱即dp[0][1]

买卖都是相同的价格相当于钱花出去了又原路返回因此dp[0][2]

3如果第0天第二次操作

所谓的“第二次买入”意味着我之前已经买入过一次了也就是说第二次买入依赖于第一次卖出的状态

又因为题目规定买完必须先卖掉才能再买所以“第二次买入”时已经经过了第一次买入和卖出

因此在第0天第二次买入时手头上的钱仍然是0那么买入之后的状态自然就是

-prices[0]

1][0];//不进行操作//第i天第一次进行操作dp[i][1]

max(dp[i

prices[i]);//不操作|买入股票用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][2]

max(dp[i

prices[i]);//不操作|卖出股票用前一天状态下还剩的钱加上第i天卖掉股票的收益//第i天第二次进行操作dp[i][3]

max(dp[i

注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。

输入k

从上题来看买卖两次已经需要列出4个状态了不算不操作状态因此在k次交易的条件下罗列处所有状态是可能的

需要使用循环去控制

因为买卖次数变成k次每多一次买卖会新增两种状态所以dp数组的大小要设置为2k

vectorvectorint

正如上面的分析k次买卖的话是不可能都列出来所有状态的因此需要进行抽象抽象出一个通用的递推公式

dp[i][0]

1][0];//不进行操作//第i天第一次进行操作dp[i][1]

max(dp[i

prices[i]);//不操作|买入股票用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][2]

max(dp[i

prices[i]);//不操作|卖出股票用前一天状态下还剩的钱加上第i天卖掉股票的收益//第i天第二次进行操作dp[i][3]

max(dp[i

prices[i]);//不操作|卖出股票这里可以发现二维dp数组中第二个维度我们是写成具体数字的用来表示买入和卖出状态

1表示买入j

prices[i]);//不操作|奇数买入,用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][j]

max(dp[i

prices[i]);//不操作|偶数卖出,用前一天状态下还剩的钱加上第i天卖掉股票的收益

如果j

在第0天第一次买入初始现金为0那么现在要扣除买股票的钱即dp[0][1]

3如果第0天第二次操作

即j为奇数时候要初始化为-prices[0]j为偶数时候要初始化为0

使用for循环进行初始化

-prices[0];//0在创建dp数组的时候就初始化了所以不用在此处初始化}//遍历dp数组for(int

prices.size();

2){//不操作|奇数买入,用前一天状态下还剩的钱减去第i天买入股票的价格dp[i][j

max(dp[i

prices[i]);//不操作|偶数卖出,用前一天状态下还剩的钱加上第i天卖掉股票的收益dp[i][j

max(dp[i