①可以无限次购买②同一时刻只能持有一支股票

$f[i][0/1]$代表第i天结束时不持有/持有股票的最大利润

$f[i][0] = max(f[i – 1][0], f[i – 1][1] + prices[i – 1])$

$f[i][1] = max(f[i – 1][1], f[i – 1][0] – prices[i – 1])$

注意：前一天的结束 = 后一天的开始

$f[0][0] = 0, f[0][1] = -inf$, 因为在$f[1][0] = max(f[0][0], f[0][1] + prices[i – 1])$中第一天不可能卖出股票

答案$f[n][0]$，因为$f[n][0]$一定大于$f[n][1]$

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        int f[length + 1][2];
        f[0][0] = 0, f[0][1] = -1e9;
        for(int i = 1;i < length + 1;i++){
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i - 1]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i - 1]);
        }
        return f[length][0];
    }
};