当前位置：首页 > 洛谷 > 洛谷P1121题解：动态规划求解环形数组最大子段和问题（附代码注释）

洛谷P1121题解：动态规划求解环形数组最大子段和问题（附代码注释）

3个月前 (07-08)

一、题目解读

洛谷P1121题要求求解环形数组的最大子段和，即在一个环形数组中找到一个连续子段，使其元素和最大。环形数组的特殊性在于首尾元素可相连，需考虑线性子段与跨越首尾的环形子段两种情况。

二、解题思路

采用动态规划，分“线性情况”与“环形情况”处理。

1. 线性情况：通过两次遍历，分别计算从左到右、从右到左的最大子段和（前缀和、后缀和），并组合两者得到不跨越首尾的最大线性子段和。

2. 环形情况：利用“总和-最小子段和”的策略，计算环形子段和。通过两次反向计算最小子段和，得到跨越首尾的最大环形子段和。

3. 特殊处理：若数组全为负数，直接返回最大元素。

三、解题步骤

1. 读取输入并计算元素总和。

2. 计算线性情况：

○ 从左到右动态更新当前最大子段和（prefix_max）。

○ 从右到左动态更新当前最大子段和（suffix_max）。

○ 遍历组合两者的和，得到线性情况最大值。

3. 计算环形情况：

○ 类似线性情况，计算最小子段和（prefix_min, suffix_min）。

○ 遍历时通过总和尚前缀和+后缀和得到环形子段和，并取最大值。

4. 比较线性与环形结果，返回较大者。

四、代码与注释

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    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(circular_max, linear_max) < 0) {
        int max_val = *max_element(a.begin(), a.end());
        return cout << max_val << endl;
    }
    
    // 返回较大值
    cout << max(linear_max, circular_max) << endl;
}