使用 javascript 的最大子数组

Question

给定一个整数数组 nums，

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

它的总和最大，return它的总和。

示例：

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

Output: 6

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

Inputs:[-1]

Output:-1

Inputs:[-2,-1]

Outputs:[-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]))

使用 javascript 的最大子数组

Maximum Subarray using javascript

javascript

kadanes-algorithm