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

题目

给定 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;
}