当前位置:首页 > 洛谷 > 洛谷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问题提供了典型思路。


原创内容 转载请注明出处

分享给朋友:

相关文章

力扣LCR182:字符串操作三连 从基础拼接到底层指针优化

力扣LCR182:字符串操作三连 从基础拼接到底层指针优化

题目重解需要将密码字符串从第target个字符开始进行重新排列,形成新的动态密码。例如输入"password"和target=3,结果应为"swordpas"。...

力扣第71题:用栈轻松解决Unix路径简化问题

力扣第71题:用栈轻松解决Unix路径简化问题

题目解读:在Unix风格的文件系统中,我们经常需要处理各种复杂的路径表示。给定一个绝对路径字符串,我们需要将其转换为最简化的规范路径。规范路径要求:路径始终以斜杠'/'开头;两个目录名...

力扣654:递归分治的艺术 如何用最大元素构建二叉树

力扣654:递归分治的艺术 如何用最大元素构建二叉树

题目重解我们面对一个看似简单却充满递归魅力的题目:给定一个不含重复元素的整数数组,需要构建一棵特殊的二叉树。这个树的每个父节点都必须是当前子数组中的最大元素,而它的左右子树则分别由该最大值左侧和右侧的...

【动态规划入门】力扣509题:斐波那契数列的经典解法与优化思路

【动态规划入门】力扣509题:斐波那契数列的经典解法与优化思路

题目解读‌斐波那契数列是一个经典的数学问题,在计算机科学中常被用作算法教学的入门案例。这个神奇的数列从0和1开始,后续每个数字都是前两个数字之和。题目要求我们计算第n个斐波那契数,看似简单的问题背后却...

力扣540题:线性扫描法如何高效定位唯一数

力扣540题:线性扫描法如何高效定位唯一数

题目重解一个严格递增的有序数组中,除某个元素外,其余每个元素均出现两次。这个看似简单的条件背后隐藏着巧妙的规律——单一元素会打破数组的"成对对称性"。题目要求以O(log n)时间...

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

一、题目解读2019年CSP-J的“纪念品”问题(对应洛谷P5662)要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品,需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化...

发表评论

访客

看不清,换一张

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