题解思路

状态机动态规划建模

本题可以看作是一个状态机 DP问题，每个下标 i 都有两种状态：

• 状态 $s_1(i)$：必须以下标 $i$ 结尾的子段最大和 即当前子段必须包含 $a_i$，对应 dp[i][1]。
• 状态 $s_0(i)$：前 $i$ 个元素中的全局最大子段和

题目描述：

给定一个整数序列 $a_1, a_2, \dots, a_n$，其中 $n$ 为整数序列的长度。请你计算出该序列的最大子段和，即从该序列中选出一个连续的子序列，使得子序列的和最大。请注意，子序列的长度可以为 1，且可以是整个序列。

输入：

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示序列的长度。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(-10^4 \leq a_i \leq 10^4)$，表示序列中的元素。

输出：

输出一个整数，表示最大子段和。

样例输入：

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

样例输出：

6

提示：

在上面的例子中，最大子段和为 6，对应的子序列为 $[4, -1, 2, 1]$。