[数据结构与算法]leetcode 309

思路

首先将购买股票的价格作为收益的一部分，其必然为负值；对于每一天的收益与是否持有股票、是否购买入股票、是否卖出股票有关，这三者的状态也决定了明天的收益，也取决于昨天这三者的状态。
1.记dp0[i]为第i天持有股票的最大收益，因为股票可能是当天买入的，也可能是昨天就持有的，所以dp0[i]的值与dp1[i-1]和dp2[i-1]均相关
2.记dp1[i]为第i天卖出股票的最大收益，要想在第i天卖出股票，那么第i-1天就必须持有股票，dp1[i]与dp[i-1]相关
3.记dp2[i]为第i天不持有股票的最大收益，如果第i天不持有股票，那么可能是第i-1天就将股票卖出或者第i-1天就不持有股票，即dp2[i]与dp2[i-1]和dp1[i-1]相关

状态迁移方程
dp0[i]=max{dp0[i-1],dp2[i-1]-prices[i]}
dp1[i]=dp0[i-1]+prices[i]
dp2[i]=max{dp1[i-1],dp2[i-1]}

实现

可以对一维数组dp进行状态压缩，只保留前一天的状态

代码`

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length=prices.size();
        int dp0=(-1)*prices[0];
        int dp1=0;
        int dp2=0;
        for(int i=1;i<length;i++)
        {
            int last0=dp0;
            int last1=dp1;
            int last2=dp2;
            dp0=last0>last2-prices[i]?last0:last2-prices[i];
            dp1=last0+prices[i];
            dp2=last1>last2?last1:last2;
        }
        return dp1>dp2?dp1:dp2;
    }
};