OJ lintcode 最小子数组

作者: DayDayUpppppp | 来源:发表于2017-02-19 20:04 被阅读10次

    给定一个整数数组,找到一个具有最小和的子数组。返回其最小和。
    注意事项
    子数组最少包含一个数字
    您在真实的面试中是否遇到过这个题?
    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;
    
        }
    };
    
    

    相关文章

      网友评论

        本文标题:OJ lintcode 最小子数组

        本文链接:https://www.haomeiwen.com/subject/oqwjwttx.html