openjudge 8464
这道题其实很简单，算是DP的基础题，比较适合开拓DP思维。
题目比较有欺骗性，其实稍微想想就可以解决，因为题意说第一次卖出后才能买入，所以我们可以考虑枚举断点，所以题目一下变得简单，我们线性扫两遍，算最大值就好了。
具体为：
由于不能同时进行两次交易，所以枚举断点，一遍扫做1到n的前n个的最大值，由于最大值一定是单调递增的，所以每次读入新的a[i]，判断是否有更优解就好了，同理，一遍扫n到1的后n个的最大值，做同样的事，然后枚举断点取最大值。
代码如下：
#include<stdio.h>
int T,n,a[],f[],g[],ans;
int main()
{
scanf("%d",&T);
while(T--)
{
int best=-,temp=;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
if(a[i]<temp)
temp=a[i];
if(a[i]-temp>best)
best=a[i]-temp;
f[i]=best;
}
best=-,temp=-;
for(int i=n;i>=;i--)
{
if(a[i]>temp)
temp=a[i];
if(temp-a[i]>best)
best=temp-a[i];
g[i]=best;
}
for(int i=;i<=n;i++)
if(f[i]+g[i]>ans)ans=f[i]+g[i];
printf("%d\n",ans);
ans=;
}
return ;
}