我要评论
题目：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例：
- 输入： n u m s = [ − 2 , 1 , − 3 , 4 , − 1 , 2 , 1 , − 5 , 4 ] nums = [-2,1,-3,4,-1,2,1,-5,4] nums=[−2,1,−3,4,−1,2,1,−5,4]
- 输出： 6 6 6
- 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。
解题思路：贪心策略
每遍历一个数，就用count加上，若count < 0则舍弃，从下一个元素开始统计。然后统计的过程中，寻找最大值。
class solution {
public:
int maxsubarray(vector<int>& nums) {
int res = int_min;
int count = 0;
for(int i = 0; i < nums.size(); i++){
count += nums[i];
if(count > res) res = count;
if(count < 0){
count = 0;
continue;
}
}
return res;
}
};
发表评论