洛谷P1121题解：环形数组最大两段子段和的高效解法

2天前洛谷题解56

一、问题分析

题目要求在一个环形数组中找到两个不相交的子段，使它们的和最大。这个问题可以分解为两种情况：

线性情况：两段都在数组的同一侧
环形情况：两段跨越数组的首尾

二、算法核心思路

预处理：

计算数组总和
预处理前缀/后缀最大子段和
预处理前缀/后缀最小子段和

线性情况处理：

使用Kadane算法计算从左到右和从右到左的最大子段和
组合前缀和后缀最大值

环形情况处理：

计算总和减去最小两段子段和
使用类似方法处理最小子段和

特殊情况处理：

处理全负数数组的情况

三、完整代码实现（带注释）

#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;
}