欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LintCode 41. 最大子数组 JavaScript算法

程序员文章站 2022-07-15 23:35:13
...

描述

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。

说明

子数组最少包含一个数

样例

- 样例1:

输入:[2,2,3,4,1,2,1,5,3]
输出:6
解释:符合要求的子数组为[4,1,2,1],其最大和为 6- 样例2:

输入:[1,2,3,4]
输出:10
解释:符合要求的子数组为[1,2,3,4],其最大和为 10

挑战

要求时间复杂度为O(n)

解析

const maxSubArray = function (nums) {
    if (nums === null || nums.length === 0) {
        return 0;
    }
    var maxSum = nums[0], minSum = 0, sum = 0;
    var i;
    for (i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (sum - minSum > maxSum) {
            maxSum = sum - minSum;
        }
        if (sum < minSum) {
            minSum = sum;
        }
    }
    return maxSum;
}

运行结果

LintCode 41. 最大子数组 JavaScript算法