思路:
动态规划
- dp[i][0] 表示第i天持有股票所得现金。
- dp[i][1] 表示第i天不持有股票所得最多现金
递推式:
● 第i-1天就持有股票,保持现状,dp[i][0]=dp[i-1][0]
● 第i天买入股票,就是第i-1天不持有股票最大利润-price[i]:dp[i][0]=dp[i-1][1]-price[i]
dp[i][0]选最大的,dp[i][0]=max(dp[i-1][0],dp[i-1][1]-price[i])
(2)如果第i天不持有股票,即dp[i][1]是第i天不持有股票获得的最多的现金
●如果第i天卖出,dp[i][1]=price[i]+dp[i-1][0]
理解:第i天卖出说明,第i-1天持有股票,获得收益为前i-1天的收益+第i天的收益
●如果第i天不卖出,说明已经卖出去,收益和第i-1天相同,dp[i][1]=dp[i-1][1]
dp[i][1]取最大的,dp[i][1]=max(dp[i-1][1],price[i]+dp[i-1][0]);