利用 JavaScript 查找最长的非负和序列

问题

我们需要编写一个 JavaScript 函数来接收一个包含一组整数的数组，每个元素包含在 -1 到 1 之间的可能值。

我们的函数应该返回该序列中和大于或等于零的最长子序列的大小。

示例

以下是代码 -

 实时演示

const arr = [-1, -1, 0, 1, 1, -1, -1, -1];
const longestPositiveSum = (arr = []) => {
   let sum = 0;
   let maxslice = 0;
   let length = arr.length;
   const sumindex = [];
   let marker = length * 2 + 1;
   for(let i = 0; i < length * 2; i++){
      sumindex[i] = marker;
   }
   for(let i = 0; i < arr.length; i++){
      sum += arr[i];
      if (sum >= 0)
         maxslice = i + 1;
      else if (sumindex[sum+length] != marker)
         maxslice = Math.max(maxslice, i - sumindex[sum+length]);
      else
         sumindex[sum+length] = i;
   };
   return maxslice;
};
console.log(longestPositiveSum(arr));

输出

5

AmitDiwan

更新日期： 2021 年 4 月 19 日

154 个浏览量

开启你的 职业生涯

完成课程获得认证

开始学习