给定一个整数数组,找到一个具有最小和的子数组。返回其最小和。
注意事项
子数组最少包含一个数字
您在真实的面试中是否遇到过这个题?
Yes
样例
给出数组[1, -1, -2, 1],返回 -3
class Solution {
public:
/**
* @param nums: a list of integers
* @return: A integer denote the sum of minimum subarray
*/
int minSubArray(vector<int> nums) {
// write your code here
int sum=0; //记录当前最小的结果
int min=0; //记录最小的结果
int p_min=nums[0];
int flag=0;
for(int i=0;i<nums.size();i++){
sum=sum+nums[i];
if(sum>0){
sum=0;
}
else{
if(min>sum){
min=sum;
}
}
//记录数组中的最小的元素
if(p_min>nums[i]){
p_min=nums[i];
}
if(nums[i]<0){
flag=-1; //如果flag==-1 ,也就是说明其中有一个元素是负数
}
}
if(flag==-1){
return min; //这是存在有负数的情况
}
else{
return p_min; //这是所有元素都为整数的情况
}
//return min< p_min ? min:p_min;
}
};
网友评论