本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

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