算法:找到一个具有最大和的连续子数组

原创
前端路迹
2019-9-11 09:27
编辑于 2020-4-6 11:18

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
function maxSubArray(arr) {

    var max = arr[0], sum = arr[0], start = 0, end = 0, lastStart = 0

    for (var i = 1; i < arr.length; i++) {

        if (sum < 0) {
            sum = arr[i]
            start = i
        } else {
            sum = arr[i] + sum
        }

        if (sum > max) {
            lastStart = start
            end = i
            max = sum
        }
    }

    if (start > end) {
        start = lastStart
    }

    return [max, JSON.stringify(arr.slice(start, end + 1))]
}

console.log(maxSubArray([10, -5, -6, 2, 3, 1]))    //  [10, "[10]"]

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   //  [6, "[4,-1,2,1]"]

console.log(maxSubArray([2, 10, -5, -11, 1, 2, -100, 100]))  // [100, "[100]"]
转载请注明出处。本文地址: https://www.qinshenxue.com/article/2019-09-11-09-27-59.html
关注我的公众号