PTA-101b-数据结构（连续子序列最大和、输出 1 ~ n）

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

分数 25

作者 陈越

单位 浙江大学

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

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

• 数据 0~6：测试基本正确性；
• 数据 7：103 个随机整数；
• 数据 8：104 个随机整数；
• 数据 9：105 个随机整数。

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

11
1 4

解析

#include <iostream>
using namespace std;
#define MAX 100000
int main ()
{
    int n;
    cin >> n;
    int *a = new int[MAX];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int max_sum = 0, current_sum = 0;
    int start = 0, end = 0;
    int current_start = 0;
    for (int i = 0; i < n; i++)
    {
        current_sum += a[i]; 
        if (current_sum > max_sum)
        {
            max_sum = current_sum;
            start = current_start;
            end = i;
        }
        if (current_sum < 0)
        {
            current_sum = 0;
            current_start = i + 1;
        }

    }
    if (max_sum == 0)
    {
        cout <<"0\n-1 -1\n";
    }
    else
    {
        printf("%d\n%d %d\n", max_sum, start , end );
    }
    free(a);
    return 0;
}

注意

要彻底理解 “连续子序列最大和” 的 C 语言实现，我们需要从问题本质、算法选择、代码结构、核心逻辑、边界处理五个维度逐步拆解，结合具体案例让每一步都清晰可追溯。

一、问题本质与算法选择

1. 问题核心需求

给定 n 个整数序列，需找到：

• 所有连续子序列的和中的最大值（称为 “最大和”）；
• 该子序列的首尾下标（从 0 开始），若有多个解，选下标最小的；
• 特殊规则：若所有元素非正（全负或全零），最大和为0（对应 “空子列”），下标为-1 -1。

2. 算法选择：Kadane 算法

为什么不用暴力法（枚举所有子序列，O (n²) 复杂度）？因为题目中 n 最大为 10⁵，暴力法会执行约 10¹⁰次操作，严重超时。而Kadane 算法通过 “动态维护当前子序列和”，只需遍历 1 次数组（O (n) 复杂度），能高效处理大规模数据。

二、完整代码结构拆解

代码整体分为 5 个模块：头文件引入→输入处理→变量初始化→核心遍历计算→结果输出，我们逐个拆解。

c运行

#include <stdio.h>   // 输入输出函数（scanf/printf）
#include <stdlib.h>  // 动态内存分配（malloc/free）

int main() {
    // 1. 读取序列长度n
    int n;
    scanf("%d", &n);
    
    // 2. 动态分配数组（存储n个整数）
    int *a = (int *)malloc(n * sizeof(int));
    if (a == NULL) return 1;  // 内存分配失败（OJ环境可忽略）
    
    // 3. 读取n个整数到数组
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    
    // 4. 初始化关键变量
    int max_sum = 0;          // 全局最大和（默认空子列的0）
    int current_sum = 0;      // 当前正在累加的子序列和
    int max_start = -1;       // 全局最大子序列的起始下标
    int max_end = -1;         // 全局最大子序列的结束下标
    int current_start = 0;    // 当前子序列的起始下标
    
    // 5. 核心遍历：计算最大子序列和及下标
    for (int i = 0; i < n; i++) {
        current_sum += a[i];  // 步骤1：将当前元素加入当前子序列
        
        // 步骤2：若当前和大于全局最大和，更新全局信息
        if (current_sum > max_sum) {
            max_sum = current_sum;    // 更新全局最大和
            max_start = current_start;// 记录当前子序列的起始下标
            max_end = i;              // 记录当前子序列的结束下标（即i）
        }
        
        // 步骤3：若当前和为负，重置当前子序列（从下一个元素重新开始）
        else if (current_sum < 0) {
            current_sum = 0;          // 重置当前和为0（重新累加）
            current_start = i + 1;    // 下一个子序列的起始下标是i+1
        }
        
        // 步骤4：若当前和 == 全局最大和，不更新（保留首次出现的最小下标）
    }
    
    // 6. 输出结果
    if (max_sum == 0) {
        // 情况1：所有元素非正（全局最大和仍为初始0）
        printf("0\n");
        printf("-1 -1\n");
    } else {
        // 情况2：存在正的最大和
        printf("%d\n", max_sum);
        printf("%d %d\n", max_start, max_end);
    }
    
    // 7. 释放动态内存（避免内存泄漏）
    free(a);
    return 0;
}

三、关键变量作用详解

每个变量的设计都对应算法逻辑，理解它们是掌握代码的关键：

变量名	初始值	作用
max_sum	0	存储全局最大和，初始为 0（对应 “空子列” 的默认最大和）。
current_sum	0	存储当前正在累加的子序列和，每次遍历都更新，不合适时重置。
max_start	-1	存储全局最大子序列的起始下标，初始为 - 1（空子列的默认下标）。
max_end	-1	存储全局最大子序列的结束下标，初始为 - 1（空子列的默认下标）。
current_start	0	存储当前子序列的起始下标，当前子序列被放弃时，更新为下一个元素下标。

四、核心遍历逻辑逐行解析

遍历循环（for (int i = 0; i < n; i++)）是算法的核心，我们结合测试样例（输入：10 -10 2 2 3 4 -5 -23 4 7 -21）逐步拆解：

测试样例数组：a[0]=-10, a[1]=2, a[2]=2, a[3]=3, a[4]=4, a[5]=-5, a[6]=-23, a[7]=4, a[8]=7, a[9]=-21

1. 基础操作：current_sum += a[i]

将当前元素a[i]加入 “当前子序列” 的和中，相当于 “继续扩展当前子序列”。

2. 关键判断 1：if (current_sum > max_sum)

当 “当前子序列和” 超过 “全局最大和” 时，说明找到了更优的子序列，需更新全局信息。

• 样例过程：
  • i=1（a[1]=2）：current_sum=2 > 0，更新max_sum=2，max_start=1，max_end=1；
  • i=2（a[2]=2）：current_sum=4 > 2，更新max_sum=4，max_end=2；
  • i=3（a[3]=3）：current_sum=7 > 4，更新max_sum=7，max_end=3；
  • i=4（a[4]=4）：current_sum=11 > 7，更新max_sum=11，max_end=4；
  • 后续i=5~9的current_sum均未超过 11，故max_sum最终为 11，下标为1~4。

3. 关键判断 2：else if (current_sum < 0)

当 “当前子序列和” 为负数时，说明这个子序列已经 “无价值”—— 继续往后加元素，只会让和更小（比如当前和为 - 10，加下一个元素 2，和为 - 8，不如直接从 2 开始新子序列）。

• 样例过程：
  • i=0（a[0]=-10）：current_sum=-10 < 0，重置current_sum=0，current_start=1（下一个子序列从 i=1 开始）；
  • i=6（a[6]=-23）：current_sum=11-5-23=-17 < 0，重置current_sum=0，current_start=7；
  • i=9（a[9]=-21）：current_sum=4+7-21=-10 < 0，重置current_sum=0，current_start=10（超出数组范围，无影响）。

4. 隐含逻辑：current_sum == max_sum

当 “当前子序列和” 等于 “全局最大和” 时，不更新全局下标 —— 因为题目要求 “解不唯一时输出最小下标”，首次出现的子序列已经记录了最小下标，后续相同和的子序列无需处理。

五、边界情况处理

代码需覆盖所有特殊场景，确保结果符合题目要求：

场景 1：全负序列（如输入3 -5 -3 -1）

• 遍历过程中，current_sum始终为负（-5→重置→-3→重置→-1→重置），max_sum保持初始值 0；
• 输出：0和-1 -1（空子列结果）。

场景 2：单元素正（如输入1 8）

• i=0时，current_sum=8 > 0，更新max_sum=8，max_start=0，max_end=0；
• 输出：8和0 0。

场景 3：单元素负（如输入1 -6）

• current_sum=-6 < 0，重置后max_sum仍为 0；
• 输出：0和-1 -1。

场景 4：混合序列（有正有负，但最大和为正）

• 如样例，最终输出正的最大和及对应下标。

六、效率与安全性说明

1. 时间效率：O (n)，仅遍历 1 次数组，10⁵个元素可在毫秒级完成计算；
2. 空间效率：O (n)，用动态内存malloc存储数组（避免静态数组栈溢出，栈空间通常仅几 MB，10⁵个 int 约 400KB，堆空间足够）；
3. 内存安全：用free(a)释放动态内存，避免内存泄漏。

七、测试样例完整流程回顾

输入样例的遍历过程可总结为下表，清晰看到变量变化：

i	a[i]	current_sum	max_sum	max_start	max_end	current_start
0	-10	-10→0	0	-1	-1	1
1	2	2	2	1	1	1
2	2	4	4	1	2	1
3	3	7	7	1	3	1
4	4	11	11	1	4	1
5	-5	6	11	1	4	1
6	-23	-17→0	11	1	4	7
7	4	4	11	1	4	7
8	7	11	11	1	4	7
9	-21	-10→0	11	1	4	10

最终输出：

11
1 4

通过以上拆解，不仅能理解代码 “怎么写”，更能明白 “为什么这么写”，后续遇到类似问题（如子序列最大和的变种）也能灵活调整。

算法1-10~11 输出 1 ~ n

分数 10

作者 陈越

单位 浙江大学

给定正整数 n，输出 1 ~ n，每个数字占一行。

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

• 数据 0：测试基本正确性；
• 数据 1：n=1；
• 数据 2：n=1000；
• 数据 3：n=10000；
• 数据 4：n=100000；
• 数据 5：n=1000000。

输入格式:

输入在一行中给出正整数 n (≤106)。

输出格式:

输出 1 ~ n，每个数字占一行。

输入样例:

3

输出样例:

1
2
3

解析

#include <stdio.h>

int main() {
    // 只加这1行！设置输出缓冲区为16KB，减少printf的交互次数
    setvbuf(stdout, NULL, _IOFBF, 16384);
    
    int n;
    scanf("%d", &n);
    
    // 循环和之前完全一样，没变化
    for (int i = 1; i <= n; i++) {
        printf("%d\n", i);
    }
    
    return 0;
}

注意

为什么加这 1 行就不超时了？（简单解释）

原来的 printf 是 “每次打印都直接告诉系统输出”，1e6 次打印就要麻烦系统 1e6 次，很慢；加了 setvbuf(stdout, NULL, _IOFBF, 16384) 后：

• 系统会先在内存里开一个 “16KB 的小仓库”（缓冲区）；
• 每次 printf 的内容（比如 “1\n”“2\n”）先存到这个 “仓库” 里；
• 等 “仓库” 装满了，再一次性告诉系统 “把仓库里的内容全输出”；
• 这样 1e6 次打印，最后只需要和系统交互几十次（16KB 能装很多行数字），速度就快多了。

这行代码怎么记？（不用死记，理解意思）

• stdout：指 “标准输出”（就是我们平时打印的内容）；
• _IOFBF：表示 “全缓冲”（先存满缓冲区再输出）；
• 16384：缓冲区大小（16KB，这个数字不用改，直接用就行）。

测试效果

之前简单版跑 n=1e6 可能超时，加了这行后：

• 循环逻辑没变，还是大二能看懂的 for 循环；
• 运行时间会从几秒降到几十毫秒，完全能通过 OJ 的时间限制。

万一还是超时？（再加 1 行优化输入）

如果 n 特别大，scanf("%d", &n) 也可能有点慢，再补 1 行优化输入缓冲，代码还是很简单：

c运行

#include <stdio.h>

int main() {
    // 优化输出缓冲（关键）
    setvbuf(stdout, NULL, _IOFBF, 16384);
    // 优化输入缓冲（可选，进一步提速）
    setvbuf(stdin, NULL, _IOFBF, 16384);
    
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        printf("%d\n", i);
    }
    
    return 0;
}

总结

这个优化方案的优点：

1. 简单：只加 1-2 行代码，原有逻辑（循环、printf）完全不变，大二能轻松理解；
2. 高效：解决 1e6 规模的超时问题，原理好解释（“先存再批量输出”）；
3. 通用：以后写其他循环输出的题目，加这行都能提速。

不用害怕 “优化”，这个级别的优化本质就是 “让系统少跑几趟腿”，记住 setvbuf(stdout, NULL, _IOFBF, 16384) 这行 “提速魔法” 就行～