题解 | #子数组最大连续和#

从头遍历输入数组，先假设数组中元素不全为负。
每次都将当前元素加到sum中，然后判断，sum，若sum<0，则令sum=0。因为之后sum必定已经加到或将会加到一个不为负的数。若sum>max，则令max=sum。
然后对数组全为负的情况添加一些判断。此时max必定为负，则当sum<0且max<0时，若sum>max，令max=sum，然后令sum=0(这块测试用例不完善, 不令sum=0也可提交通过。感兴趣的可以输入{4, -3 -1 -2 -4}自行测试)。

这个题在数据类型方面埋了一个坑，题目中给出|ai|<=10^9，所以输入的数据是有可能会超出int类型的范围的。最开始时所有的数子都是用int类型保存的，在提交时卡在第9个用例过不去，第9个用例的数据量又非常大，无法进行调试。导致我一度认为是我的判断逻辑出了问题，在看了别人通过的代码后发现使用的都是long long类型，这才恍然大悟。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int length;
    cin >> length;
    vector<long long> arr(length);
    for(int i = 0;i < arr.size();i++){
        cin >> arr.at(i);
    }
    if(length == 1){
        cout << arr.at(0);
        return 0;
    }
    long sum = 0;
    long max;
    for(int i = 0;i < arr.size();i++){
        if(arr.at(i) >= 0 && sum < 0){
            sum = 0;
        }
        sum += arr.at(i);
        if(!i){
            max = sum;
            sum = 0;
        }
        if(sum < 0 && max >= 0){
            sum = 0;
        }
        else if(sum < 0 && max < 0){
            if(sum >= max){
                max = sum;
            }
            else{
                sum = 0;
            }
        }
        else{
            if(sum > max){
                max = sum;
            }
        }
    }
    cout << max;
    return 0;
}

看了别人的代码后，发现单独将输入数组全部为负数的情况拿出来处理会使代码逻辑更为清晰，可读性更好，这里也改写一下代码，将数组全部为负数的情况提前单独处理。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int length;
    cin >> length;
    vector<long long> arr(length);
    for(int i = 0;i < arr.size();i++){
        cin >> arr.at(i);
    }
    if(length == 1){
        cout << arr.at(0);
        return 0;
    }
    long long sum = 0;
    long long max;
    int minus = 0;
    while(minus < length){
        if(arr.at(minus) >= 0){
            break;
        }
        minus++;
    }
    if(minus == length){
        int m = arr.at(0);
        for(int i = 0;i < arr.size();i++){
            if(arr.at(i) > m){
                m = arr.at(i);
            }
        }
        cout << m;
        return 0;
    }
    for(int i = 0;i < arr.size();i++){
        sum += arr.at(i);
        if(!i){
            max = sum;
        }
        if(sum < 0){
            sum = 0;
        }
        else if(sum > max){
            max = sum;
        }
    }
    cout << max;
    return 0;
}