其实做这题我一眼DP...
设\(f[i]\)表示前\(i\)天能够获得的最大利润（肯定未持股）
有\(f[i]=max(f[i-1],a[i]-a[j]+f[j-1])\)，第一个决策表示未在当天购入股票
稍微优化即可，复杂度为\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=2e9;
int n,a,Max=-INF;
int f[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
f[i]=max(f[i-1],a+Max);
Max=max(Max,f[i-1]-a);
}
printf("%d",f[n]);
return 0;
}
顺便提一嘴，我看了一下贪心的解法，发现就是将差分数组的所有正数加了起来。这在允许多次买卖同一只股票的情况下不难理解。但我转念一想，我的dp好像没有考虑这种情况。但后面发现无所谓，其实多个正数挨在一起时可以通过一次交易（即最开始买入，最后卖出）来获利