การใช้อัลกอริทึม Kadane หาผลรวมสูงสุดของอาร์เรย์ย่อยใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของจำนวนเต็ม (ทั้งบวกและลบ) arr เป็นอาร์กิวเมนต์เดียว

ฟังก์ชันควรคืนค่าผลรวมสูงสุดของอาร์เรย์ย่อยใดๆ ในเวลาเชิงเส้น (linear time)

local_maximum ที่ดัชนี i ใดๆ คือค่าสูงสุดระหว่าง arr[i] และผลรวมของ arr[i] กับ local_maximum ที่ดัชนี i - 1

นี่คือสิ่งที่เราจะนำไปใช้เพื่อหาผลรวมอาร์เรย์ย่อยสูงสุดภายในอาร์เรย์ในเวลาเชิงเส้น

ตัวอย่างเช่น หากอินพุตคือ

อินพุต

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

เอาต์พุต

const output = 6;

คำอธิบายเอาต์พุต

เพราะอาร์เรย์ย่อยที่มีผลรวมสูงสุดคือ

[4, -1, 2, 1]

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

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSequence = (arr = []) => {
  let currentSum = 0;
  let maxSum = 0;
  for (let elem of arr) {
    const nextSum = currentSum + elem;
    maxSum = Math.max(maxSum, nextSum);
    currentSum = Math.max(nextSum, 0);
  }
  return maxSum;
};
console.log(maxSequence(arr));

ผลลัพธ์

6