题解 | #买卖股票的最好时机(二)#

/** state translat equation
f(0) = 0
f(x) = f(x-1) if v(x-1) > v(x)
f(x) = f(x-2) + v(x) - v(x-2) if v(x-1) < v(x) && left 0
f(x) = f(x-1) + v(x) - v(x-1) if v(x-1) < v(x) && left 1
*/

/**
* only need to save f(x) and f(x-1)
*/

#include <algorithm>
#include <cerrno>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        // vector<int> maxProfit(prices.size(), 0);
        int maxProfit, maxProfit_pre;
        bool bLeft = true;
        for(auto i=1; i < prices.size(); i++) {
            if(prices[i] > prices[i-1]) {
                if(bLeft) {
                    maxProfit_pre = maxProfit;
                    maxProfit = maxProfit + prices[i] - prices[i-1];
                } else {
                    int tmp = maxProfit;
                    maxProfit = maxProfit_pre + prices[i] - prices[i-2];
                    maxProfit_pre = tmp;
                }
                bLeft = false;
            } else {
                maxProfit_pre = maxProfit;
                bLeft = true;
            }
        }
        return maxProfit;
    }
};