题目描述
给定一个长度为 NN 的数组,数组中的第 ii 个数字表示一个给定股票在第 ii 天的价格,再给定一个非负整数 ff,表示交易股票的手续费用。
设计一个算法来计算你所能获取的最大利润。
你可以无限次地完成交易,但是你每次交易都需要支付手续费。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
输入格式
第一行包含两个整数 NN 和 ff,分别表示数组的长度以及每笔交易的手续费用。
第二行包含 NN 个不超过 1000010000 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
样例
6 2
1 3 2 8 4 9
算法思路
(动态规划) $O(n)$
我们维护两个变量b和s,前者表示当我们不持有股票时的最大利润,后者表示当我们持有股票时的最大利润。
在第 i 天时,我们需要根据第i−1 天的状态来更新b和s的值。对于 b,我们可以保持不变,或者将手上的股票卖出,状态转移方程为
$ b = max(b, s + p[i] - m) $,其中p为股票价格数组,m为交易费用
对于s,我们可以保持不变,或者买入这一天的股票,状态转移方程为
$ s = max(s, b - p[i]) $
在计算这两个状态转移方程时,我们可以不使用临时变量来存储第i−1 天b 和s 的值,而是可以先计算b 再计算 s,原因是在同一天卖出再买入(亏了一笔手续费)一定不会比不进行任何操作好。
C++ 代码
#include <iostream>
using namespace std ;
const int N = 100010 ;
int p[N] ;
int n,m ;
int main(){
cin>>n>>m ;
for(int i=0;i<n;i++){
cin>>p[i] ;
}
int b = 0,s = -p[0] ;//b不持有股票,s买入股票
for(int i=1;i<n;i++){
b = max(b,s+p[i]-m) ;
s = max(s,b-p[i]) ;
}
cout<<b<<endl ;
return 0 ;
}