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

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

2天前

洛谷P1121题解:动态规划求解环形数组最大子段和问题(附代码注释) 洛谷题解 动态规划 环形结构 前缀和 后缀和 C++ 第1张

一、题目解读

洛谷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;
}

五、总结

该解法通过动态规划高效处理环形数组的最大子段和问题,关键在于对线性与环形情况的分解,以及巧妙利用“总和-最小子段和”转换环形问题。代码逻辑清晰,兼顾了边界处理,为同类环形DP问题提供了典型思路。


原创内容 转载请注明出处

分享给朋友:

相关文章

NOIP2005 普及组 洛谷P1408 背包问题的空间优化技巧与实战应用

NOIP2005 普及组 洛谷P1408 背包问题的空间优化技巧与实战应用

题目重解想象你是一名药师,有t分钟在山上采集m种草药。每种草药需要time分钟采集,价值为num。这就像考试时分配时间做题,要选择收益最大的题目组合。题目要求计算在规定时间内能获得的最大草药价值。解题...

手搓顺序表类代码注释与详解:从零实现动态数组(新手教程)

一、简介和特点顺序表(Sequential List)是数据结构中基础的一种线性表,其特点是将数据元素存储在连续的内存空间中。通过数组实现,支持随机访问(即通过索引直接访问元素),适用于频繁随机读取的...

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

一、题目解读题目要求在一个n×m的网格中,从左上角到右下角选择一条路径,路径上的数字可重复取用,求取数之和的最大值。路径限制为仅能向右或向下移动。需注意路径的灵活性与重复取数的可能性,传统单向动态规划...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

一、题目解读牛客25461题要求计算一个花园中n朵花到两个喷泉的最小距离平方和。用户需输入喷泉坐标(x1,y1)和(x2,y2),以及n朵花的坐标(x,y),通过合理分配每朵花到两个喷泉的距离,使总距...

标题:洛谷B3617题解析:八进制转十六进制算法实现与优化(附AC100代码)

标题:洛谷B3617题解析:八进制转十六进制算法实现与优化(附AC100代码)

一、题目解读洛谷B3617题要求将输入的八进制字符串转换为十六进制表示。题目需处理大数场景,且对输入合法性有明确限制(长度不超过1000,仅包含0-7字符)。由于八进制与十六进制无法直接转换,需借助十...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。