题意 给定整数序列，求连续非空子数组的最大和。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路 用贪心 Kadane 算法，维护当前段和、全局最大值。逐个遍历，每次选择另起一段或接上前段，不断更新最大值，一遍遍历即可求出答案，时间复杂度 O (n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完整代码

这道题一眼看上去是一道经典的区间和最大值，但是实际上用普通方法会直接 TLE ，因为太慢了！！！，那这样该怎么做呢？我们可以使用 Kadane 算法进行优化，不过，这道题里出现了负数值，所以可能会导致最大和变量里的值是负的，那不如直接将这个值改变为当前的数，如max(a,sum+a),之后用这个值和最终答案打擂就行，代码如下 注意，这里的 sum，sum1 都要处理负数值，所以应初始化为极小值