题解 | #买卖股票的最好时机(二)#
买卖股票的最好时机(二)
https://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9
/** 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
*/
