题目解析：寻找两个不相交连续子数组的最大和

问题描述

给定一个整数数组，要求找到两个不相交的连续子数组，使得这两个子数组的和之和最大。这两个子数组不能重叠，且每个子数组至少包含一个元素。

解题思路

1. 预处理最大子数组和：

   • 从左到右计算每个位置的最大子数组和（leftMax数组）
   • 从右到左计算每个位置的最大子数组和（rightMax数组）

2. 计算最终结果：

   • 遍历数组，对于每个位置i，计算leftMax[i]（0到i的最大子数组和）和rightMax[i+1]（i+1到n-1的最大子数组和）的和
   • 找出所有这些和中的最大值

关键步骤说明

1. leftMax数组计算：

   • currentMax记录以当前元素结尾的最大子数组和
   • leftMax[i]记录从数组开始到i位置的最大子数组和

2. rightMax数组计算：

   • 同理，从右向左计算
   • rightMax[i]记录从i位置到数组末尾的最大子数组和

3. 结果计算：

   • 遍历所有可能的分割点i
   • 将数组分为[0,i]和[i+1,n-1]两部分
   • 取两部分最大子数组和的最大和

复杂度分析

• 时间复杂度：O(n) 每个测试用例
• 空间复杂度：O(n) 用于存储预处理数组

示例分析

输入：

1
10
1 -1 2 2 3 -3 4 -4 5 -5

处理过程：

1. leftMax数组：[1,1,3,5,8,5,9,5,10,5]
2. rightMax数组：[10,9,10,8,6,9,5,5,5,-5]
3. 计算结果：
   • 在i=4时，leftMax[4]=8，rightMax[5]=5
   • 8+5=13为最大值

输出：

13

总结

该算法通过预处理左右最大子数组和，然后线性扫描得到最终结果，高效地解决了问题。适用于大规模数据输入（$n≤50000$）。

标程

#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;

const int MAXN = 50010;
int arr[MAXN];
int leftMax[MAXN];
int rightMax[MAXN];

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; ++i) {
			scanf("%d", &arr[i]);
		}
		
		// Compute leftMax: maximum subarray sum from left to right
		int currentMax = arr[0];
		leftMax[0] = arr[0];
		for (int i = 1; i < n; ++i) {
			currentMax = max(arr[i], currentMax + arr[i]);
			leftMax[i] = max(leftMax[i-1], currentMax);
		}
		
		// Compute rightMax: maximum subarray sum from right to left
		currentMax = arr[n-1];
		rightMax[n-1] = arr[n-1];
		for (int i = n-2; i >= 0; --i) {
			currentMax = max(arr[i], currentMax + arr[i]);
			rightMax[i] = max(rightMax[i+1], currentMax);
		}
		
		// Compute d(A)
		int result = INT_MIN;
		for (int i = 0; i < n-1; ++i) {
			result = max(result, leftMax[i] + rightMax[i+1]);
		}
		printf("%d\n", result);
	}
	return 0;
}