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 最大子数组||

    给定一个整数数组,找出两个 不重叠 子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的...

  • lintcode 最大子数组|||

    给定一个整数数组和一个整数 k,找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续...

  • lintcode 最大子数组

    给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。样例给出数组[−2,2,−3,4,−1,2,1,−5,...

  • 最大子数组

    最大子数组(lintcode 41) 描述:给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。样例:给出...

  • lintcode 最大子数组差

    给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。...

  • OJ lintcode 最大子数组

    给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。注意事项子数组最少包含一个数您在真实的面试中是否遇到过...

  • LintCode 41. 最大子数组

    题目描述 给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。 子数组最少包含一个数。挑战:要求时间复杂度...

  • 动态规划

    求最大子数组,最大子乘积

  • Leetcode-Medium 152. Maximum Pro

    题目描述 给定一个整数数组nums(有正有负),求最大子数组乘积 思路 求最大子数组乘积问题是求最大子数组之和演变...

  • LeetCode-152-乘积最大子数组

    LeetCode-152-乘积最大子数组 152. 乘积最大子数组[https://leetcode-cn.com...

网友评论

    本文标题:lintcode 最大子数组

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