PTA 算法1-7~9 连续子序列最大和

算法1-7~9 连续子序列最大和

分数 25

作者 陈越

单位 浙江大学

给定 n 个整数组成的序列 { a1,a2,⋯,an }，“连续子序列”被定义为 { ai,ai+1,⋯,aj }，其中 1≤i≤j≤n。“连续子序列最大和”则被定义为所有连续子序列元素的和中最大者。例如给定序列 { -2, 11, -4, 13, -5, -2 }，其连续子序列 { 11, -4, 13 } 有最大的和 20。请编写程序，计算给定整数序列的连续子序列最大和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

  • 数据 0~6：测试基本正确性；
  • 数据 7：10$^3$ 个随机整数；
  • 数据 8：10$^4$ 个随机整数；
  • 数据 9：10$^5$ 个随机整数。

输入格式:

输入第一行给出正整数 n (≤105)；第二行给出 n 个整数，绝对值均不超过 100，其间以空格分隔。

输出格式:

在第一行中输出连续子序列最大和，第二行输出该子序列首尾的数组下标（从 0 开始），以 1 个空格分隔。若解不唯一，则输出最小的数组下标（如样例所示）。
注意：如果序列中所有整数皆为零或负数，则取空子列的结果是最大的，为 0；此时空子序列数组首尾的下标均为 -1。

输入样例:

1
2
10
-10 2 2 3 4 -5 -23 4 7 -21

输出样例:

1
2
11
1 4

自己写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n); // 定义一个存放整数的容器
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int max_sum = 0; // 定义连续子序列最大和
    int current_sum = 0; // 定义当前的和
    int best_start = -1; // 定义连续子序列最大和起始下标
    int best_end = -1; // 定义连续子序列最大和终点下标
    int current_start = 0; // 定义当前位置

    for (int i = 0; i < n; i++) {
        current_sum += a[i];
        if (current_sum > max_sum) { // 如果当前最大值比全局的还大
            max_sum = current_sum; // 更新全局最大值
            best_start = current_start; // 把起始下标赋值
            best_end = i; // 把当前遍历的i赋值给best_end:表示现在是最大的
        } else if (current_sum < 0) {
            current_sum = 0; // 都为负了肯定先置为0
            current_start = i + 1; // 从下一个开始
        }
    }
    if (max_sum == 0) { // 如果全是负数或0，则max_sum始终为0
        cout << 0 << endl; 
        cout << "-1 -1";
    } else {
        cout << max_sum << endl;
        cout << best_start << " " << best_end;
    }

}

一、C++ 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 1. 读取序列长度 n
    int n;
    cin >> n;

    // 2. 用 vector 存储输入序列
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 3. 初始化核心变量
    int global_max = 0;          // 全局最大和（默认空子列的和为 0）
    int current_sum = 0;         // 当前正在累加的子序列和
    int best_start = -1;         // 最大和子序列的起始下标（初始对应空子列）
    int best_end = -1;           // 最大和子序列的结束下标（初始对应空子列）
    int current_start = 0;       // 当前子序列的起始下标（跟踪当前累加起点）

    // 4. 核心遍历：Kadane 算法计算最大子序列和及下标
    for (int i = 0; i < n; ++i) {
        // 步骤1：将当前元素加入当前子序列，扩展子序列范围
        current_sum += nums[i];

        // 步骤2：若当前子序列和超过全局最大和，更新全局最优解
        if (current_sum > global_max) {
            global_max = current_sum;    // 更新全局最大和
            best_start = current_start;  // 记录当前子序列的起点（保证解的唯一性）
            best_end = i;                // 记录当前子序列的终点（即当前元素下标）
        }

        // 步骤3：若当前子序列和为负，丢弃当前子序列，从下一个元素重新开始
        else if (current_sum < 0) {
            current_sum = 0;             // 重置当前和为 0，准备新的子序列
            current_start = i + 1;       // 下一个子序列的起点设为当前元素的下一个
        }

        // 隐含逻辑：若当前和等于全局最大和，不更新下标（保留首次出现的最小下标）
    }

    // 5. 按题目要求输出结果
    if (global_max == 0) {
        // 所有元素非正（全局最大和未被更新），输出空子列结果
        cout << 0 << endl;
        cout << -1 << " " << -1 << endl;
    } else {
        // 存在正的最大和，输出最大和及对应首尾下标
        cout << global_max << endl;
        cout << best_start << " " << best_end << endl;
    }

    return 0;
}

二、核心逻辑深度解析

1. 算法选择：为什么用 Kadane 算法？

题目中序列长度

而 Kadane 算法通过 “动态维护当前子序列和”，仅需遍历 1 次数组（时间复杂度 O (n)），既能高效处理大规模数据，又能同步记录最大和子序列的首尾下标，完美适配题目的需求。

2. 关键变量作用（算法的 “核心骨架”）

每个变量的设计都服务于 “计算最大和” 与 “记录下标” 两个核心目标，具体作用如下：

变量名 初始值 核心作用
global_max 0 存储全局范围内的最大子序列和，初始值设为 0（对应题目 “空子列最大和为 0” 的规则）。
current_sum 0 存储 “以当前元素结尾的子序列和”，动态更新（扩展子序列）或重置（丢弃无效子序列）。
best_start -1 存储最大和子序列的起始下标，初始为 -1（对应空子列的默认下标）。
best_end -1 存储最大和子序列的结束下标，初始为 -1（对应空子列的默认下标）。
current_start 0 存储 “当前正在累加的子序列” 的起始下标，当子序列被丢弃时，更新为下一个元素的下标。

3. 遍历过程逐步拆解（结合示例理解）

以输入 10 -10 2 2 3 4 -5 23 4 7 -21 为例，拆解遍历过程中变量的变化，清晰理解算法逻辑：

（1）初始状态

global_max=0，current_sum=0，best_start=-1，best_end=-1，current_start=0。

（2）遍历到 i=0（元素 -10）

  • current_sum += -10 → current_sum = -10；
  • 因 current_sum < 0，执行重置：current_sum=0，current_start=1；
  • 此时 global_max 仍为 0，不更新下标。

（3）遍历到 i=1（元素 2）

  • current_sum += 2 → current_sum = 2；
  • 因 2 > 0（global_max），更新：global_max=2，best_start=1，best_end=1。

（4）遍历到 i=4（元素 4）

  • 逐步累加后，current_sum = 2+2+3+4 = 11；
  • 因 11 > 2，更新：global_max=11，best_end=4（best_start 仍为 1）。

（5）遍历到 i=6（元素 23）

  • 累加前 current_sum = 11 + (-5) = 6，加 23 后 → current_sum=29；
  • 因 29 > 11，更新：global_max=29，best_end=6（best_start 仍为 1）。

（6）遍历到 i=8（元素 7）

  • 累加后 current_sum = 29+4+7 = 40；
  • 因 40 > 29，更新：global_max=40，best_end=8。

（7）遍历到 i=9（元素 -21）

  • 累加后 current_sum = 40 -21 = 19；
  • 因 19 < 40 且 19 > 0，不更新 global_max，也不重置。

4. 特殊情况处理（覆盖题目所有规则）

情况 1：所有元素非正（如输入 3 -5 -3 -1）

  • 遍历过程中，current_sum 始终为负（或 0），每次累加后都会重置为 0；
  • 最终 global_max 仍为初始值 0，触发 “输出 0 和 -1 -1” 的逻辑，符合 “空子列” 规则。

情况 2：单元素为正（如输入 1 8）

  • 遍历后 current_sum=8 > 0，更新 global_max=8，best_start=0，best_end=0；
  • 输出 8 和 0 0，符合要求。

情况 3：存在多个相同最大和（如输入 5 1 2 -1 2 1）

  • 首次出现最大和（如 3：1+2）时，已记录下标 0 1；
  • 后续出现相同和（如 2+1=3）时，因 current_sum == global_max，不更新下标，保证 “最小下标” 的要求。

三、C++ 特性的优势体现

  1. vector 动态数组：无需预先定义固定大小，直接根据输入的 n 创建数组，避免空间浪费；且无需手动释放内存，函数结束时会自动销毁，安全性更高。
  2. cin/cout 输入输出：语法简洁，无需关注格式化符号（如 %d），直接匹配变量类型，降低代码出错概率。
  3. 代码可读性：变量命名和逻辑结构更贴合 C++ 编程习惯，后续维护或扩展时（如增加子序列打印功能）更便捷。

四、最终测试结果

输入 10 -10 2 2 3 4 -5 23 4 7 -21，输出如下，与预期一致：

1
2
40
1 8