前缀和优化（Kadane 算法）

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

#include <iostream>
using namespace syh;
int main()
{
    long long n,sum=-100000000000000, a, sum1=-1111111111111110;
    cin>>n;
    for(int i = 1;i<=n;i++)
        {
            cin>>a;
            sum1=max(a, sum1+a);
            sum=max(sum,sum1);
        }
    cout<<sum;
}

注意，这里的 sum，sum1 都要处理负数值，所以应初始化为极小值