ผลรวมของ subarray สูงสุดในอาร์เรย์แบบวงกลมโดยใช้ 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));