主页 / 问题 / 1376646
Accepted
Konstantin_SH
Asked:2022-06-30 19:40:33 +0000 UTC2022-06-30 19:40:33 +0000 UTC

为什么 Kadane 算法问题没有通过一些测试？

  • 772

我解决代码大战的问题。要求找到子数组的最大和。我已经阅读了有关 Cadenet 算法的信息，并且我认为我已经实现了它。我的函数通过了简单的测试，但没有通过一些attempt. 帮助我理解为什么。这是我的代码：

let maxSequence = function(arr){
  // ...
  if (arr.length === 0) return 0;
  let result = arr[0];
  let sum = arr[0];
  
  
  for (let i =0; i < arr.length; i++){
    if (arr[i] === []) arr[i] = 0;
    sum = Math.max(arr[i], arr[i] + sum)
    result = Math.max(result, sum)
  }
  return result;
}

它从这里失败了 17 次测试。对我来说最令人惊讶的是，该实现据称不适用于负数，尽管在简单的测试中有这样的数字并且算法正确地找到了总和。

javascript

1 个回答

  1. Best Answer

    使固定：

    let result = 0;
let sum = 0;

    这是通过测试的 Python 代码：

    def max_sequence(arr):
    summ = 0
    ans = 0
    for x in arr:
        summ = max (summ + x, 0)
        ans = max (ans, summ)
    return max(ans, 0)
    • 2

相关问题