【PTA数据结构 | C语言版】连续子序列最大和

本专栏持续输出数据结构题目集，欢迎订阅。

题目

给定 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 (≤10^5 )；第二行给出 n 个整数，绝对值均不超过 100，其间以空格分隔。

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

输入样例:
10
-10 2 2 3 4 -5 -23 4 7 -21

输出样例:
11
1 4

代码

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[100000];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    int current_sum = 0;  // 当前子序列的和
    int max_sum = 0;      // 全局最大子序列和
    int start = -1;       // 最大子序列起始下标
    int end = -1;         // 最大子序列结束下标
    int temp_start = 0;   // 当前候选子序列的起始下标
    
    // 标记序列中是否存在正数，用于处理全非正数的情况
    int has_positive = 0;  

    // 遍历数组，动态计算最大子序列和
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) has_positive = 1;  // 存在正数则标记为真
        
        // 如果当前子序列和为负，重置为0并更新候选起始位置
        if (current_sum < 0) {
            current_sum = 0;
            temp_start = i;  // 从当前位置开始新的子序列
        }
        
        current_sum += arr[i];  // 累加当前元素
        
        // 当新的子序列和更大时，更新全局最优解
        if (current_sum > max_sum) {
            max_sum = current_sum;
            start = temp_start;
            end = i;
        }
    }
    
    // 处理全非正数的特殊情况
    if (!has_positive) {
        printf("0\n-1 -1\n");
    } else {
        printf("%d\n%d %d\n", max_sum, start, end);
    }
    
    return 0;
}