122. 买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II

如果之前持有股票，那今天可以卖出或者不卖出。卖出后状态变为今天没持有股票。

如果之前没有股票，今天可以买入或不买入，买入就变成了今天持有了股票。

dp

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int have = -prices[0];
        int nothave = 0;
        int sz = prices.size();
        for(int i = 1; i < sz; ++i)
        {
            auto price = prices[i];
            have = max(have, nothave - price);
            nothave = max(have + price, nothave); // 这里之所以不用怕have受到上面的have影响是因为。假如受到了影响，就说明nothave-price比have要大，所以nothave要大于have+price，而此时have+price=nothave,所以不会影响结果
        }
        return nothave;
    }
};

直接计算所有的上坡，贪心

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