3068: 股票买卖DP

解题思路:两次买卖， 求最大区间差

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
const int N = 1e5 + 10;
int a[N],f1[N],f2[N],t,n;
int main()
{
	cin >> t;
	while(t --){
		memset(a, 0, sizeof a);
		memset(f1, -0x3f, sizeof f1);
		memset(f2, -0x3f, sizeof f2);
		cin >> n;
		for(int i = 1; i <=n; i ++ ) cin >> a[i];
		int mi = 0x3f3f3f3f, mx = -0x3f3f3f3f;
		for(int i = 1; i <= n; i ++) {
			mi = min(mi, a[i]);
			f1[i] = max(f1[i-1],a[i] - mi);
		}
		for(int i = n; i >= 1; i --){
			mx = max(mx,a[i]);
			f2[i] = max(f2[i+1],mx - a[i]);
		}
		int ans = -0x3f3f3f3f;
		for(int i = 1; i <= n ; i ++)
			ans = max(ans, f1[i] + f2[i]);
		cout << ans << endl;
	}
	return 0;
}