子数组最大累加和

思路：sum记录每一段的总和，如果sum<0,说明前面的基础只会使后面的和变小，此时把sum置为0；
如果sum>=0,则前面的值的和，对后面的数有利，应该在此基础上加上后面的数。
每次新加一个数，把ans和sum比较，把大的值放入ans中。
最后ans中的值，即为答案。
代码如下

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        int sum=0,ans=0;  //sum记录状态，ans存最终答案
        for(int i=0;i<arr.size();i++){
            sum+=arr[i];  
            if(sum<0) sum=0;   //如果sum<0的话，不要再此基础上增加，把sum置为0；
            ans=max(sum,ans);  //状态转移方程
        }
        return ans;
    }
};