题目描述
每次 买+卖 算一个transaction,收一次fee
样例
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
算法1
(DP) $O(n)$
C++ 代码
// 题意是说 买+卖算一个transaction,在卖出时收一次fee
// f[i]: 第i天结束时不持有股票的最大收益
// g[i]: 第i天结束时持有股票的最大收益
// f[i] = max( f[i-1], x[i] - fee + g[i-1] ), 第i天 什么都不做,或者卖股票,则前一天要持有
// g[i] = max( g[i-1], -x[i] + f[i-1] ), 第i天 什么都不做,或者买股票,则前一天不能持有
// f[0]=0, f[0]=-x[0]
int maxProfit(vector<int>& x, int fee) {
int n = x.size();
if(n<=1) return 0;
vector<int> f(n, 0), g(n, 0);
f[0] = 0, g[0] = -x[0];
for(int i=1; i<n; i++) {
f[i] = max( f[i-1], x[i] - fee + g[i-1] );
g[i] = max( g[i-1], -x[i] + f[i-1] );
}
return f[n-1];
}