javascript - 使用javascript的最大子数组

Question

给定一个整数数组 nums，

找到连续的子数组（至少包含一个数字）

其中有最大的总和并返回它的总和。

例子：

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

输出：6

解释：[4,-1,2,1] 的最大和 = 6。

输入：[-1]

输出：-1

输入：[-2,-1]

输出：[-1]

我在我的 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

Answer 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]))