说明

给定一个长度为 n 的整数序列 a_1, a_2, \dots, a_n，请你找出其中**连续子段**的最大和。 例如，序列 -2, 1, -3, 4, -1, 2, 1, -5, 4 中，最大子段和为 6（对应子段 [4, -1, 2, 1]）。

输入格式

第一行，整数 n（1 \le n \le 10^5）。 第二行，n 个整数 a_i（-10^4 \le a_i \le 10^4），空格分隔。

输出格式

一行，最大子段和。

9
-2 1 -3 4 -1 2 1 -5 4

6

提示

**核心思想**：如果当前的累加和变成负数，就舍弃它，从下一个数重新开始。 设 `cur` 表示以当前位置结尾的最大子段和： - 如果 `cur + a[i]` 还不如 `a[i]` 本身大（即 `cur < 0`），那么 `cur = a[i]` - 否则 `cur = cur + a[i]` 每一步更新全局最大值： ans = cur = a[0] for x in a[1:]: if cur ans: ans = cur print(ans) 时间复杂度 O(n)，空间复杂度 O(1)。这比暴力枚举 O(n^2) 快得多！ **思考**：为什么 `cur