最大连续数列和

问题描述

对于一个有正有负的整数数组，请找出总和最大的连续数列。
给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。
测试样例：

[1,2,3,-6,1]
返回：6

解题思路

如果前n个数之和已经是负数就没必要在加了。
[1,2,3,-6,1]
[1,3,6,0,1]
最大为6

class MaxSum {
public:
    int getMaxSum(vector<int> A, int n) {
        // write code here
        int ans = A[0];
        int sum = A[0];
        for (int i=1;i<A.size();i++){
            if (sum<0) sum= A[i];
            else if (sum>=0) sum+=A[i];        
            if (ans<sum) ans=sum;  
        }  
        return ans;
    }
};