北京网页设计与网站建设,网络营销方式有哪些?举例说明,西安市城乡建设管理局网站6,音乐网站网页设计题1#xff1a;
指路#xff1a;123. 买卖股票的最佳时机 III - 力扣#xff08;LeetCode#xff09;
思路与代码#xff1a;
买卖股票专题中三者不同的是Ⅰ为只买卖一次#xff0c;Ⅱ可多次买卖#xff0c;Ⅲ最多可买卖两次。那么我们将买买卖行为分为五个状态部分(…题1
指路123. 买卖股票的最佳时机 III - 力扣LeetCode
思路与代码
买卖股票专题中三者不同的是Ⅰ为只买卖一次Ⅱ可多次买卖Ⅲ最多可买卖两次。那么我们将买买卖行为分为五个状态部分(可延续前几天已有的状态之前说过分两种情况可延续前面已经买入/卖出也可以是今天才买入/卖出)。定义一个数组dp[i][j]其中i为第i天j为第j个状态那么dp[i][j]的含义为第i天在状态j的情况下手头的最大现金。那么从j开始讨论当j0时表示这一天对股票无操作当j1时表示第一次持有当j2时表示第一次卖出当j3时表示第二次买入当j4时表示第二次卖出。因为卖出状态时永远比买入状态时手头现金多所以我们在第一次卖出和第二次卖出中求得较大值。在递推公式部分第i天无操作的股票状态延续前一天即dp[i][0]dp[i-1][0]第一天买入的股票状态就是在前面说的延续状态和新开状态中取较大值即dp[i][1]max(dp[i-1][1], dp[i-1][0]-prices[i])类似得出第一次卖出第二次买入和第二次卖出的情况。注意的是买入的时候要减去股票的买入金额(因为求的是手头的金额)卖出的时候要加上股票的卖出金额(卖出后手头就有钱了)。代码如下
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;vectorvectorint dp(prices.size(), vectorint(5, 0));dp[0][1] -prices[0]; // 第一次买入dp[0][3] -prices[0]; // 第二次买入 for (int i 1; i prices.size(); i) {dp[i][0] dp[i - 1][0];dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]); // 首次卖出dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]); // 二次卖出}return max(dp[prices.size() - 1][2], dp[prices.size() - 1][4]);}
};
