【GESP】C++五级练习（贪心思想考点） luogu-P1115 最大子段和

GESP C++ 五级练习题，贪心和前缀和/Kadane算法考点。题目难度⭐⭐★☆☆，五级来说难度偏简单。洛谷难度等级普及−

luogu-P1115 最大子段和

题目要求

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

4

说明/提示

样例 1 解释

选取 $[3, 5]$ 子段 ${3, -1, 2}$，其和为 $4$。

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^3$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。

---

题目分析

这道题目要求我们找到一个数列中连续子段的最大和。比如数列 2 -4 3 -1 2 -4 3，最大子段是 3 -1 2，和为 4。

我们可以从两种角度来思考：贪心策略（动态规划） 和 前缀和。

方法一：贪心策略（Kadane算法）

核心思想： “正向增益，负向舍弃”。

想象我们在遍历数组，一边走一边累加数值（记为 current_sum）。

1. 累加判断： 如果之前的 current_sum 是正数（> 0），说明它对当前的数字有“增益”效果（加上它会让结果更大），因此我们将当前数字加入到这个子段中。
2. 重新开始： 如果之前的 current_sum 是负数或零（<= 0），说明它对当前数字是“拖累”（加上它反而变小了）。此时，我们果断舍弃之前的子段，以当前数字为起点重新开始计算 current_sum。

在遍历过程中，时刻维护一个全局最大值 max_sum，每次更新 current_sum 后都与 max_sum 比较并取较大值。

方法二：前缀和优化

核心思想： “区间和等于前缀和之差，减去最小得最大”。

1. 前缀和性质： 记 pre_a[i] 为数组前 $i$ 个数的和。那么，任意子段 [j, i] 的和可以表示为 pre_a[i] - pre_a[j-1]。
2. 寻找最大值： 当我们遍历到位置 $i$ 时，pre_a[i] 已经固定。为了让子段和 pre_a[i] - pre_a[j-1] 最大，我们需要让减数 pre_a[j-1] 尽可能小。
3. 算法流程： 我们从左到右遍历，一边计算当前的前缀和 pre_a[i]，一边记录在此之前出现过的最小前缀和（min_pre）。
   • 以当前位置 $i$ 结尾的最大子段和 = pre_a[i] - min_pre。
   • 用这个结果更新全局最大值。
   • 随时更新 min_pre，保持它是当前遇到的最小值。

---

示例代码

方法一、Kadane算法

#include <algorithm>
#include <iostream>
#include <vector>

int a[200005];

int main() {
    int n;
    std::cin >> n;  // 输入序列长度

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 动态规划思想 (Kadane算法)
    // current_sum 相当于 dp[i]，表示以当前元素结尾的最大子段和
    // max_sum 记录全局最大的子段和

    long long current_sum = a[0];
    long long max_sum = a[0];

    for (int i = 1; i < n; ++i) {
        // 核心代码注释：
        // 如果之前的子段和 current_sum >
        // 0，说明它对当前元素有增益，因此将当前元素加入该子段。
        // 否则（current_sum <=
        // 0），之前的子段和对当前元素无增益甚至有负面影响，
        // 所以抛弃之前的子段，从当前元素 a[i] 重新开始计算子段。
        if (current_sum > 0) {
            current_sum += a[i];
        } else {
            current_sum = a[i];
        }

        // 每次更新完 current_sum 后，尝试更新全局最大值 max_sum
        max_sum = std::max(max_sum, current_sum);
    }

    std::cout << max_sum << std::endl;

    return 0;
}

方法二、前缀和(本质其实一样)

#include <climits>
#include <cmath>
#include <iostream>

// 定义数组用于存储输入数据和前缀和
// 大小设为 200005，满足题目 N <= 200000 的要求
int ary[200005];
int pre_a[200005];

int main() {
    int n;
    std::cin >> n;  // 输入序列长度

    // 输入数据并计算前缀和
    // pre_a[i] 表示从第 1 个数加到第 i 个数的和
    for (int i = 1; i <= n; i++) {
        std::cin >> ary[i];
        if (i == 1) {
            pre_a[i] = ary[i];  // 第一个元素的前缀和就是它本身
        } else {
            pre_a[i] = pre_a[i - 1] +
                       ary[i];  // 后续元素的前缀和 = 前一个前缀和 + 当前元素
        }
    }

    int max_sum = INT_MIN;  // 初始化最大和为最小整数

    // last_idx 变量的作用：
    // 我们希望找到一个位置 k (k < i)，使得 pre_a[k] 最小。
    // 这样 pre_a[i] - pre_a[k] (即子段和) 就能最大。
    // 这里 last_idx - 1 就代表了这个“最小前缀和”的下标。
    // 初始时 last_idx = 1，即 last_idx - 1 = 0，pre_a[0] = 0。
    int last_idx = 1;

    // 枚举子段的终点 i (从 1 到 n)
    // 注意：i 在这里代表子段的结束位置
    for (int i = 1; i <= n; i++) {
        // 1. 计算以 i 结尾的最大子段和
        //    子段和 = pre_a[i] - pre_a[last_idx - 1]
        //    其中 pre_a[last_idx - 1] 是我们在 i 之前遇到的最小前缀和
        max_sum = std::max(max_sum, pre_a[i] - pre_a[last_idx - 1]);

        // 2. 维护最小前缀和的位置
        //    如果当前的前缀和 pre_a[i] 比我们之前记录的最小前缀和还要小
        //    (或者相等) 那么对于后面 (i+1, i+2...) 的元素来说，减去 pre_a[i]
        //    会得到更大的子段和 所以我们更新 last_idx 为 i + 1 (这样下一次循环
        //    last_idx - 1 就是 i)
        if (pre_a[i] <= pre_a[last_idx - 1]) {
            last_idx = i + 1;
        }
    }

    std::cout << max_sum << std::endl;  // 输出结果
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号