OJ lintcode 最小子数组

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

    }
};

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。注意事项子数组最少包含一个数您在真实的面试中是否遇到过...
    DayDayUpppppp阅读 437评论 0 0
  • 题目 给定一个整数数组,找到一个具有最小和的子数组。返回其最小和。 ** 注意事项子数组最少包含一个数字 ** 样...
    六尺帐篷阅读 1,576评论 0 1
  • 题目前的数字是对应的lintcode的题目序号 14.二分查找 给定一个排序的整数数组(升序)和一个要查找的整数t...
    mytac阅读 749评论 1 2
  • 3.10 69.给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问) 二叉树的层次遍历样例给一棵二叉树 {3...
    mytac阅读 1,126评论 3 3
  • *面试心声:其实这些题本人都没怎么背,但是在上海 两周半 面了大约10家 收到差不多3个offer,总结起来就是把...
    Dove_iOS阅读 27,282评论 30 472