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

ปัญหา

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

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

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