题目大意

    给定一列数，从中选择两个不相交的连续子段，求这两个连续子段和的最大值。

题目分析

    典型的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
     
      #include
      
       #define MAX_LEN 50005#define INFINITE 1 << 30#define max(a, b) a > b? a:blong 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;}