ผลรวมอาร์เรย์ย่อยสูงสุดในอาร์เรย์วงกลมด้วย JavaScript

ปัญหา

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

เราสามารถมองอาร์เรย์ arr นี้ว่าเป็นอาร์เรย์วงกลม ซึ่งหมายถึงองค์ประกอบตัวสุดท้ายจะตามด้วยตัวแรก ฟังก์ชันควรหาและคืนค่าผลรวมสูงสุดที่เป็นไปได้ของอาร์เรย์ย่อยที่ไม่ว่างของ arr

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

อินพุต

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

เอาต์พุต

const output = 4;

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

เพราะอาร์เรย์ย่อยที่ต้องการคือ [3, -1, 2]

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

const arr = [2, -2, 3, -1];
const maxSubarraySumCircular = (arr = []) => {
  let max = arr[0];
  let min = arr[0];
  let currentMax = max;
  let currentMin = min;
  let sum = arr[0];
  for (let i = 1; i < arr.length; i++) {
    currentMax = arr[i] + Math.max(currentMax, 0);
    max = Math.max(max, currentMax);
    currentMin = arr[i] + Math.min(currentMin, 0);
    min = Math.min(min, currentMin);
    sum += arr[i];
  }
  return max < 0 ? max : Math.max(max, sum - min);
};
console.log(maxSubarraySumCircular(arr));

ผลลัพธ์

4