Tìm dãy con không âm dài nhất trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng chứa dãy số nguyên, mỗi phần tử có giá trị từ -1 đến 1. Hàm sẽ trả về độ dài của dãy con dài nhất có tổng lớn hơn hoặc bằng 0.

Ví dụ

Dưới đây là mã nguồn:

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));

Kết quả

5