题解思路
状态机动态规划建模
本题可以看作是一个状态机 DP问题，每个下标 i 都有两种状态：
- 状态 s1(i)：必须以下标 i 结尾的子段最大和
即当前子段必须包含 ai，对应
dp[i][1]。
- 状态 s0(i)：前 i 个元素中的全局最大子段和
P3905.最大子段和
题目描述：
给定一个整数序列 a1,a2,…,an，其中 n 为整数序列的长度。请你计算出该序列的最大子段和，即从该序列中选出一个连续的子序列，使得子序列的和最大。请注意，子序列的长度可以为 1，且可以是整个序列。
输入：
输入的第一行包含一个整数 n (1≤n≤105)，表示序列的长度。
输入的第二行包含 n 个整数 a1,a2,…,an (−104≤ai≤104)，表示序列中的元素。
输出：
输出一个整数，表示最大子段和。
样例输入：
9
-2 1 -3 4 -1 2 1 -5 4
样例输出：
6
提示：
在上面的例子中，最大子段和为 6，对应的子序列为 [4,−1,2,1]。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
