答案:<pre class="brush:cpp;toolbar:false">//解法1:
//基本解法
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int t, n, ans, a[N], de[N], db[N], dpe[N], dpb[N];
int main()
{
int mn, mx;
scanf("%d", &t);
while(t--)
{
memset(dpe, 0, sizeof(dpe));
memset(dpb, 0, sizeof(dpb));
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
mn = a[1];
for(int i = 1; i <= n; ++i)
{
mn = min(mn, a[i]);
de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。
dpe[i] = max(dpe[i-1], de[i]);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
mx = a[n];
for(int i = n; i >= 1; --i)
{
mx = max(mx, a[i]);
db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。
dpb[i] = max(dpb[i+1], db[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值
for(int i = 1; i < n; ++i)//枚举分割点
ans = max(ans, dpe[i]+dpb[i+1]);
printf("%d\n", ans);
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//优化:变递推为迭代
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int t, n, ans, mn, mx, a[N], dpe[N], dpb[N];
int main()
{
scanf("%d", &t);
while(t--)
{
memset(dpe, 0, sizeof(dpe));
memset(dpb, 0, sizeof(dpb));
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
mn = a[1];
for(int i = 1; i <= n; ++i)
{
mn = min(mn, a[i]);
dpe[i] = max(dpe[i-1], a[i] - mn);//第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
mx = a[n];
for(int i = n; i >= 1; --i)
{
mx = max(mx, a[i]);
dpb[i] = max(dpb[i+1], mx - a[i]);//第i到第n个数字构成的所有区间中,区间差值最大的区间的区间差值。
}
ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值
for(int i = 1; i < n; ++i)//枚举分割点
ans = max(ans, dpe[i]+dpb[i+1]);
printf("%d\n", ans);
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法2:
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int t, n, mn, mx, mxde, ans, a[N], de[N], db[N];
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
mn = a[1];
for(int i = 1; i <= n; ++i)
{
mn = min(mn, a[i]);
de[i] = a[i] - mn;//以a[i]为结尾的所有区间中,区间差值的最大的区间的区间差值。
}
mx = a[n];
for(int i = n; i >= 1; --i)
{
mx = max(mx, a[i]);
db[i] = mx - a[i];//以a[i]为起始的所有区间中,区间差值的最大的区间的区间差值。
}
mxde = ans = -INF;//ans:原序列中不相交的两个区间的区间差值加和的最大值
for(int i = 1; i < n; ++i)//枚举分割点
{
mxde = max(mxde, de[i]);//mxde为第1到第i个数字构成的所有区间中,区间差值最大的区间的区间差值。
ans = max(ans, mxde + db[i+1]);
}
printf("%d\n", ans);
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法3:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 100001
#define MOD 100001
#define E 1e-12
using namespace std;
int a[N],f1[N],f2[N];
int main()
{
int t,ans;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int minn=INF,maxx=-INF;
f1[0]=0;
f2[n+1]=0;
for(int i=1;i<=n;i++)
{
minn=min(minn,a[i]);
f1[i]=max(f1[i-1],a[i]-minn);
}
for(int i=n;i>=1;i--)
{
maxx=max(maxx,a[i]);
f2[i]=max(f2[n+1],maxx-a[i]);
}
int ans=-INF;
for(int i=1;i<=n;i++)
ans=max(ans,f1[i]+f2[i]);
printf("%d\n",ans);
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法4 动态规划
#include <bits/stdc++.h>
using namespace std;
int t,n,w[100005],dp[1000005][2];
int main() {
cin>>t;//测试案例的数量
int k=2;//最大买卖次数
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
memset(dp,0,sizeof(dp));//将f数组的所有元素置为0
for(int i=0;i<=k;i++) dp[i][1]=-1e6;//将f[j][1]列中的所有元素置为负无穷大
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++){
//第j次购入股票
dp[j][0]=max(dp[j][0],dp[j][1]+w[i]);
//第j次抛售股票
dp[j][1]=max(dp[j][1],dp[j-1][0]-w[i]);
}
cout<<dp[k][0]<<endl;
}
return 0;
}</pre>
这道题暂未补解析。