子数组的最大累加和（简单但想不到）也是容许变小但保存最大值

描述

给定一个数组arr，返回子数组的最大累加和

例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.

题目保证没有全为负数的数据

[要求]

时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

示例1

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        //重点是家后面的有没有价值，就是按说不该加-2,但因为-2后面有个6可以弥补它，所以加了他。
        if(arr.size()==0) return 0;
        if(arr.size()==1) return arr[0];
        int sum=0;
        int maxsum=INT_MIN;
        for(int i=0;i<arr.size();i++){
            sum+=arr[i];
            if(maxsum<sum) maxsum=sum;
            if(sum<0) sum = 0;
        }
        return maxsum;
//         //可以有个复杂度特别高的解法，就是每个都加到最后，然后比较大小。
//         int maxsum=arr[0];
//         for(int i=0;i<arr.size();i++)
//         {
//             int tempsum = arr[i];
//             for(int j=i+1;j<arr.size();j++){
//                 if(tempsum>maxsum) maxsum = tempsum;
//                 tempsum += arr[j];
//             }
//         }
//         return maxsum;
        //时间复杂度低一点的解法的话就是
        //首先如果前面的和小于零的话，直接舍去前面那部分，重新求和。！！！！否则前面就算小也是要的。
    }
};