ผลรวมสูงสุดของ Subarray วงกลม (Maximum Sum Circular Subarray) ใน C++

ผลรวมสูงสุดของ Subarray วงกลม (Maximum Sum Circular Subarray)

ให้อาร์เรย์วงกลม C ที่แทนด้วยอาร์เรย์ A หา subarray ที่ไม่ว่างเปล่าที่มีผลรวมสูงสุด (subarray อาจครอบคลุมปลายทั้งสองของอาร์เรย์ได้) แต่แต่ละองค์ประกอบของ A ใช้ได้สูงสุด 1 ครั้ง

ตัวอย่าง: [1,-2,3,-2] → ผลลัพธ์ 3 (subarray [3])

ขั้นตอนการแก้ปัญหา

วิธีแก้คำนึงถึง 2 กรณี: subarray ปกติ (Kadane's Algorithm) และ subarray ที่ครอบปลายทั้งสอง (total - min subarray)

1. คำนวณ Kadane's Algorithm สำหรับ max subarray ปกติ
2. คำนวณ min subarray (Kadane แบบหาค่าน้อยที่สุด)
3. คำนวณ total sum ของอาร์เรย์
4. ถ้าทุกค่าเป็นลบ คืนค่า max subarray ปกติ
5. มิฉะนั้น คืนค่า max( max_subarray, total - min_subarray )

ตัวอย่างโค้ด C++ (วิธีที่เข้าใจง่ายกว่า)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        int maxSum = A[0], minSum = A[0], total = A[0];
        int curMax = A[0], curMin = A[0];
        
        for (int i = 1; i < n; i++) {
            curMax = max(A[i], curMax + A[i]);
            maxSum = max(maxSum, curMax);
            
            curMin = min(A[i], curMin + A[i]);
            minSum = min(minSum, curMin);
            
            total += A[i];
        }
        
        if (maxSum < 0) return maxSum; // ทุกค่าเป็นลบ
        return max(maxSum, total - minSum);
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,-2,3,-2]

Output: 3