lintcode 最大子数组

作者: yzawyx0220 | 来源:发表于2016-12-27 09:49 被阅读76次

    给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。
    样例
    给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6。
    从左到右依次相加,如果为负数舍去,为正数接着相加。
    设sum为和,那么当sum小于0时直接舍去前面所有的数,并将sum重置为0;

    class Solution {
    public:    
        /**
         * @param nums: A list of integers
         * @return: A integer indicate the sum of max subarray
         */
        int maxSubArray(vector<int> nums) {
            // write your code here
            int sum = 0,result = nums[0];
            for (int i;i < nums.size();i++) {
                sum += nums[i];
                result = max(result,sum);
                sum = max(sum,0);
            }
            return result;
        }
    };
    
    

    相关文章

      网友评论

        本文标题:lintcode 最大子数组

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