问题描述
对于一个有正有负的整数数组，请找出总和最大的连续数列。
给定一个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;
}
};
网友评论