การหาผลรวมเซิร์บอาร์เรย์สูงสุดใน O(n) ด้วย Prefix Sum ใน C++

โจทย์ปัญหา

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

ตัวอย่าง

หากอาร์เรย์นำเข้าคือ {-12, -5, 4, -1, -7, 1, 8, -3} ผลลัพธ์จะเป็น 9 (มาจากเซิร์บอาร์เรย์ {4, -1, -7, 1, 8})

อัลกอริทึม

1. คำนวณ Prefix Sum ของอาร์เรย์นำเข้า
2. กำหนดค่าเริ่มต้น: min_prefix_sum = 0, res = -infinity
3. วนลูปตั้งแต่ i = 0 ถึง n-1 (n คือขนาดอาร์เรย์):
   • cand = prefix_sum[i] - min_prefix_sum
   • ถ้า cand มากกว่า res ให้อัปเดต res = cand
   • ถ้า prefix_sum[i] น้อยกว่า min_prefix_sum ให้อัปเดต min_prefix_sum = prefix_sum[i]
4. คืนค่า res

โค้ดตัวอย่าง (C++)

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

int maximumSumSubarray(int *arr, int n) {
    int minPrefixSum = 0;
    int res = numeric_limits<int>::min();
    int prefixSum[n];
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
    for (int i = 0; i < n; i++) {
        res = max(res, prefixSum[i] - minPrefixSum);
        minPrefixSum = min(minPrefixSum, prefixSum[i]);
    }
    return res;
}

int main() {
    int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result = " << maximumSumSubarray(arr, n) << endl;
    return 0;
}

ผลลัพธ์

Result = 9

คำอธิบายเพิ่มเติม

วิธีนี้ใช้หลักการของ Prefix Sum ร่วมกับการติดตามค่า Prefix Sum ต่ำสุดที่เจอมา จะได้ความซับซ้อนด้านเวลา O(n) และความซับซ้อนด้านพื้นที่ O(n) (สามารถลดเหลือ O(1) ได้โดยไม่ต้องเก็บอาร์เรย์ Prefix Sum ทั้งหมด)