Maximum Subarray Sum (Kadane's Algorithm) ใน JavaScript

ปัญหา Maximum Subarray Sum

หา Subarray (ติดกัน) ที่มีผลรวมมากที่สุดจากอาร์เรย์ที่มีทั้งจำนวนบวกและลบ

ตัวอย่าง

const arr = [-2, -3, 4, -1, -2, 1, 5, -3];
// Max sum = 7, Subarray = [4, -1, -2, 1, 5]

Kadane's Algorithm (O(n))

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

const maximumSubarray = (arr = []) => {
  let max = -Infinity;
  let currentSum = 0;
  let maxStartIndex = 0;
  let maxEndIndex = arr.length - 1;
  let currentStartIndex = 0;
  
  arr.forEach((currentNumber, currentIndex) => {
    currentSum += currentNumber;
    
    // พบผลรวมใหม่ที่มากกว่า
    if (max < currentSum) {
      max = currentSum;
      maxStartIndex = currentStartIndex;
      maxEndIndex = currentIndex;
    }
    
    // รีเซ็ตถ้าผลรวมติดลบ
    if (currentSum < 0) {
      currentSum = 0;
      currentStartIndex = currentIndex + 1;
    }
  });
  
  return arr.slice(maxStartIndex, maxEndIndex + 1);
};

console.log(maximumSubarray(arr));

ผลลัพธ์

[ 4, -1, -2, 1, 5 ]

เวอร์ชันส่งค่าผลรวม (Standard Kadane)

const maxSubarraySum = (arr) => {
  let maxSoFar = arr[0];
  let maxEndingHere = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
};

เวอร์ชันส่งค่า Subarray (แบบสมบูรณ์)

const maxSubarray = (arr) => {
  if (!arr.length) return [];
  
  let maxSum = arr[0];
  let currentSum = arr[0];
  let start = 0, end = 0, tempStart = 0;
  
  for (let i = 1; i < arr.length; i++) {
    if (currentSum + arr[i] < arr[i]) {
      currentSum = arr[i];
      tempStart = i;
    } else {
      currentSum += arr[i];
    }
    
    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }
  
  return { subarray: arr.slice(start, end + 1), sum: maxSum };
};

console.log(maxSubarray([-2, -3, 4, -1, -2, 1, 5, -3]));
// { subarray: [4, -1, -2, 1, 5], sum: 7 }

กรณีพิเศษ: ทุกตัวเป็นลบ

console.log(maxSubarray([-5, -2, -8, -1])); 
// { subarray: [-1], sum: -1 } - เลือกตัวที่ "น้อยที่สุด" (ใกล้ศูนย์สุด)

การประยุกต์ใช้

• Stock Trading (Best time to buy/sell)
• Signal Processing
• Genomic Sequence Analysis
• Image Processing (Brightest region)