最大子段和 题解
思路
方法 1
考虑 dp。
分两种情况：
1. 这个数够大，自己成为一个子段。
2. 这个数和其他数进行组合。
显然两种情况取最大值。
没啥好说的，就是最小值设置成 0，因为可以啥也不选。
时间复杂度 O(n)O(n)O(n)。
方法 2
此题数据非常小，暴力能过。
枚举左端点和右端点，前缀和优化或者直接暴力加求区间和。
最后在所有区间和中取最大值。
时间复杂度 O(n2)O(n^2)O(n2)。
代码
别抄。
方法 1
方法 2
这里我直接用的是暴力求区间和，可以用前缀和求区间和。
