44. 最小子数组
给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。 样例 给出数组[1, -1, -2, 1]，返回 -3 思路和最大子数组的思路基本是一样的，只是正数换成负数而已，简单说一下算法流程： 初始化min=nums[0]用来记录最小值,sum=0用来计算和; 遍历数组，做下面几件事： 1.sum+=nums[i]; 把当前这个数先放入子数组。 2.比较sum和min的大小，如果sum小于min，则用sum更新min。 3.如果sum>0,那么这一定不是，抛弃前面的数组，这里的抛弃只需令sum=0即可，不再把<=i索引的数计算在内。 注意：2，3的顺序不能颠倒，一定是先判断是否要更新min，然后在判断是否要抛弃前面的数组，这个和最大子数组的思路基本是一样的，这个写法更好理解一些。
int minSubArray(vector<int> &nums) {
int sum=0;
int min=nums[0];
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
if(sum<min)
//注意这里的两个if顺序千万不能搞乱了,因为下一个if会改变sum的值
{
min=sum;
}
if(sum>0)
{
sum=0;
}
}
return min;
// write your code here
}over
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读