题解

核心算法

令 dp[i] 为必须以 i 结尾的最大和，只需比较重新开始与接在前面。

思路推导

转移为 dp[i]=max(a[i],dp[i-1]+a[i])，全局取最大。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

易错点

全负数组答案不是 0；使用 long long。

完整标程见 std/main.cpp。