子數組的最大累加和（簡單但想不到）也是容許變小但儲存最大值

描述

給定一個數組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;
        //時間複雜度低一點的解法的話就是
        //首先如果前面的和小于零的話，直接舍去前面那部分，重新求和。！！！！否則前面就算小也是要的。
    }
};