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

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

2个月前 (07-08)

洛谷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问题提供了典型思路。


原创内容 转载请注明出处

分享给朋友:

相关文章

征服力扣704题:三步掌握经典二分查找算法

征服力扣704题:三步掌握经典二分查找算法

题目重解我们面对的是算法领域最经典的二分查找问题:在一个已排序的整数数组中,快速定位目标值的位置。就像在一本按字母顺序排列的字典中查找单词,我们不需要逐页翻阅,而是通过不断折半的方式快速缩小搜索范围,...

力扣第654题:最大二叉树解题教程 用数组构造最大二叉树

力扣第654题:最大二叉树解题教程 用数组构造最大二叉树

题目解读给定一个不含重复元素的整数数组,我们需要构建一棵最大二叉树。构建规则是:数组中的最大值作为根节点,其左侧子数组构建左子树,右侧子数组构建右子树,然后递归地应用这个规则。这种构建方式体现了分治思...

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

题目重解我们面对一个经典背包问题的变体:给定n个物品,每个物品有重量w和价值v,背包容量为V。需要回答两个问题:1) 普通情况下能获得的最大价值;2) 必须恰好装满背包时的最大价值(若无法装满则输出0...

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

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

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

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

发表评论

访客

看不清,换一张

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