题目大意
给定一列数，从中选择两个不相交的连续子段，求这两个连续子段和的最大值。
题目分析
典型的M子段和的问题，使用动态规划的方法来解决。
f[i][j] 表示将A[1...i] 划分为j个不相交连续子串，且A[j]属于第i个子串，所能达到的最大子串和
g[i][j] 表示将A[1...j]划分为i个不相交连续子串，且A[j]不一定属于第i个子串，所能达到的最大子串和
f[i][j] = max{f[i-1][j] + A[i], g[i-1][j-1] + A[i]}
g[i][j] = max{g[i-1][j], f[i][j]};
进行空间优化之后：
f[j] = max{f[j], g[j-1]} + A[i]
g[j - 1] = max(g[j - 1], f[j - 1]);
注意f和g的循环层次不同.这是因为：在外部进行到第i层循环的时候，f[i][j] = max{f[i-1][j] + A[i], g[i-1][j-1] + A[i]} 中max{}中的 f[j]和g[j-1]用的是第i-1层循环的时候的 f[j]和 g[j-1]； 若写成f[j] = max(f[j] + A[i], g[j - 1] + A[i]);g[j] = max(g[j], f[j]);
则本次的g[j]变成了第i次循环的g[j]，而下次循环的 f[j] = max{} 中g[j-1]变成了第i次循环的g[j]，而不是第i-1次循环的g[j]因此，写成 g[j-1] = max(g[j-1], f[j-1]); 使得 每次执行
for (j = 1; j <= m; j++){
f[j] = max(f[j] + A[i], g[j-1] + A[i]);
g[j-1] = max(g[j-1], f[j-1]);
}
的时候， f[j]都使用第i-1层的f[j]和g[j-1]，而g[j-1]使用的是第i-1层的g[j-1]和第i层的f[j]
实现(c++)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define MAX_LEN 50005
#define INFINITE 1 << 30
#define max(a, b) a > b? a:b
long long int f[MAX_LEN];
long long int g[MAX_LEN];
int A[MAX_LEN];
/*f[i][j] 表示将A[1...i] 划分为j个不相交连续子串，且A[j]属于第i个子串，所能达到的最大子串和
g[i][j] 表示将A[1...j] 划分为i个不相交连续子串，且A[j]不一定属于第i个子串，所能达到的最大子串和
f[i][j] = max{f[i-1][j] + A[i], g[i-1][j-1] + A[i]}
g[i][j] = max{g[i-1][j], f[i][j]};
进行空间优化之后：
f[j] = max{f[j], g[j-1]} + A[i]
g[j - 1] = max(g[j - 1], f[j - 1]);
注意f和g的循环层次不同
这是因为：在外部进行到第i层循环的时候，f[i][j] = max{f[i-1][j] + A[i], g[i-1][j-1] + A[i]} 中max{}中的 f[j]和g[j-1]用的是
第i-1层循环的时候的 f[j]和 g[j-1]；
若写成
f[j] = max(f[j] + A[i], g[j - 1] + A[i]);
g[j] = max(g[j], f[j]);
则本次的g[j]变成了第i次循环的g[j]，而下次循环的 f[j] = max{} 中 g[j-1]变成了第i次循环的g[j]，而不是第i-1次循环的g[j]
因此，写成 g[j-1] = max(g[j-1], f[j-1]); 使得 每次执行
for (j = 1; j <= m; j++){f[j] = max(f[j] + A[i], g[j-1] + A[i]);g[j-1] = max(g[j-1], f[j-1]);
}
的时候， f[j]都使用第i-1层的f[j]和g[j-1]，而g[j-1]使用的是第i-1层的g[j-1]和第i层的f[j]
*/
long long int MaxSum(int m, int n){int i, j;for (i = 1; i <= n; i++){for (j = 1; j <= m; j++){f[j] = max(f[j] + A[i], g[j-1] + A[i]);g[j-1] = max(g[j-1], f[j-1]);}g[j - 1] = max(g[j - 1], f[j - 1]);}return g[m];
}int main(){int cas;scanf("%d", &cas);while (cas--){int n;scanf("%d", &n);f[0] = g[0] = 0;for (int i = 1; i <= n; i++){f[i] = g[i] = -INFINITE;scanf("%d", A + i);}long long int max_sum = MaxSum(2, n);printf("%lld\n", max_sum);}return 0;
}
