洛谷P1121题解：环形数组最大两段子段和的高效解法
一、问题分析
题目要求在一个环形数组中找到两个不相交的子段，使它们的和最大。这个问题可以分解为两种情况：
线性情况：两段都在数组的同一侧
环形情况：两段跨越数组的首尾
二、算法核心思路
预处理：
计算数组总和
预处理前缀/后缀最大子段和
预处理前缀/后缀最小子段和
线性情况处理：
环形情况处理：
计算总和减去最小两段子段和
使用类似方法处理最小子段和
特殊情况处理：
处理全负数数组的情况
三、完整代码实现（带注释）
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
ios::sync_with_stdio(false); // 加速输入输出
cin.tie(nullptr); // 解除cin与cout的绑定
int n;
cin >> n;
vector<int> a(n);
int total = 0;
// 读取输入并计算总和
for (int i = 0; i < n; ++i) {
cin >> a[i];
total += a[i];
}
// 情况1：线性情况（两段都在同一侧）
int max_single = INT_MIN;
vector<int> prefix_max(n), suffix_max(n);
// 从左到右计算最大子段和
int current = 0;
for (int i = 0; i < n; ++i) {
current = max(a[i], current + a[i]);
max_single = max(max_single, current);
prefix_max[i] = max_single;
}
// 从右到左计算最大子段和
max_single = INT_MIN;
current = 0;
for (int i = n-1; i >= 0; --i) {
current = max(a[i], current + a[i]);
max_single = max(max_single, current);
suffix_max[i] = max_single;
}
// 计算线性情况的最大值
int linear_max = INT_MIN;
for (int i = 0; i < n-1; ++i) {
linear_max = max(linear_max, prefix_max[i] + suffix_max[i+1]);
}
// 情况2：环形情况（总和减去最小子段和）
int min_single = INT_MAX;
vector<int> prefix_min(n), suffix_min(n);
// 从左到右计算最小子段和
current = 0;
for (int i = 0; i < n; ++i) {
current = min(a[i], current + a[i]);
min_single = min(min_single, current);
prefix_min[i] = min_single;
}
// 从右到左计算最小子段和
min_single = INT_MAX;
current = 0;
for (int i = n-1; i >= 0; --i) {
current = min(a[i], current + a[i]);
min_single = min(min_single, current);
suffix_min[i] = min_single;
}
// 计算环形情况的最大值
int circular_max = INT_MIN;
for (int i = 0; i < n-1; ++i) {
int sum = total - (prefix_min[i] + suffix_min[i+1]);
circular_max = max(circular_max, sum);
}
// 处理全负数情况
if (max(linear_max, circular_max) < 0) {
int first = INT_MIN, second = INT_MIN;
for (int num : a) {
if (num > first) {
second = first;
first = num;
} else if (num > second) {
second = num;
}
}
cout << first + second << endl;
return 0;
}
cout << max(linear_max, circular_max) << endl;
return 0;
}四、调试技巧
注意边界条件处理
测试全负数数组的特殊情况
验证环形情况的计算逻辑
检查数组越界问题
原创内容 转载请注明出处
