给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。
样例
给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6。
从左到右依次相加,如果为负数舍去,为正数接着相加。
设sum为和,那么当sum小于0时直接舍去前面所有的数,并将sum重置为0;
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
// write your code here
int sum = 0,result = nums[0];
for (int i;i < nums.size();i++) {
sum += nums[i];
result = max(result,sum);
sum = max(sum,0);
}
return result;
}
};
网友评论