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

/** 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
*/


#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);
        bool bLeft = true;
        for(auto i=1; i < prices.size(); i++) {
            if(prices[i] > prices[i-1]) {
                if(bLeft) {
                    maxProfit[i] = maxProfit[i-1] + prices[i] - prices[i-1];
                } else {
                    maxProfit[i] = maxProfit[i-2] + prices[i] - prices[i-2];
                }
                bLeft = false;
            } else {
                maxProfit[i] = maxProfit[i-1];
                bLeft = true;
            }
        }
        return *maxProfit.rbegin();
    }
};

状态转移方程：

/** 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

*/