การหา Subarray ที่มีผลคูณมากที่สุดใน JavaScript

บทความนี้สาธิต Kadane's algorithm แบบปรับเปลี่ยนสำหรับหา maximum product subarray (รองรับ negative numbers)

ตัวอย่าง

arr = [4, -5, 2, -3, 1, -4, 0, -3]
max product = 120 (subarray [4, -5, 2, -3])

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

const arr = [4, -5, 2, -3, 1, -4, 0, -3];

const maxProduct = (arr = []) => {
  if (arr.length === 0) {
    return 0;
  }
  let max = arr[0],
      min = arr[0],
      greatest = arr[0];
  for (let i = 1; i <= arr.length - 1; i++) {
    let tempMax = max * arr[i];
    max = Math.max(
      arr[i],
      Math.max(min * arr[i], max * arr[i])
    );
    min = Math.min(arr[i], Math.min(min * arr[i], tempMax));
    greatest = Math.max(greatest, max);
  }
  return greatest;
};

console.log(maxProduct(arr));

ผลลัพธ์

120

คำอธิบาย

เก็บ max และ min product จนถึงตำแหน่งปัจจุบัน (เพราะ negative * negative = positive)

ที่แต่ละขั้น: max = max(arr[i], max*arr[i], min*arr[i]), min = min(...)

Time: O(n), Space: O(1)