使用javascript的最大子数组 [英] Maximum Subarray using javascript

问题描述

给出一个整数数组nums

Given an integer array nums,

查找连续的子数组(包含至少一个数字)

find the contiguous subarray (containing at least one number)

具有最大的总和并返回其总和.

which has the largest sum and return its sum.

示例:

输入:[-2,1，-3,4，-1,2,1，-5,4]，

Input: [-2,1,-3,4,-1,2,1,-5,4],

输出:6

说明:[4，-1,2,1]的总和= 6.

Explanation: [4,-1,2,1] has the largest sum = 6.

输入:[-1]

输出:-1

输入:[-2，-1]

Inputs:[-2,-1]

输出:[-1]

我在JS中尝试的方法:

What i try in my JS:

 
    var maxSubArray = function(nums) {
    result=0
    negativenumber=[]
    for(i=0;i<nums.length;i++){
        if(nums[i]<0){
            negativenumber.push(nums[i]);
    }else{
      result+=nums[i];
    }
    }
    return result;
};
maxSubArray([-2,1,-3,4,-1,2,1,-5,4])//should return 6
maxSubArray([-1])//should return -1
maxSubArray([-1,-2])//should return -1

推荐答案

您可以使用 Kadane的算法.

function maxSum(arr){
  let a1 = 0
  let a2 = arr[0]
  arr.forEach((i,a) => {
    a1 = Math.max(i, a1 + i)
    a2 = Math.max(a2, a1)
  })
  return a2
}
console.log(maxSum([-2,1,-3,4,-1,2,1,-5,4]))
console.log(maxSum([-1]))
console.log(maxSum([-1,-2]))

这篇关于使用javascript的最大子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！