การหาลำดับย่อยที่มีผลรวมไม่ติดลบและยาวที่สุดใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ที่มีลำดับจำนวนเต็ม แต่ละสมาชิกมีค่าเป็น -1, 0, หรือ 1 ฟังก์ชันควรคืนคาขนาดของส่วนย่อย (sub-section) ที่ยาวที่สุดของลำดับนั้นที่มีผลรวมเป็นศูนย์หรือบวก

ตัวอย่าง

โค้ดตัวอย่างดังนี้:

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