Maximum Subarray Sum Modulo M ใน C++

ปัญหา

มีอาร์เรย์ขนาด n และจำนวนเต็ม m หาค่าสูงสุดของ (ผลรวม Subarray) mod m

ตัวอย่าง

Array = {4, 9, 2}, m = 6
Subarrays:
{4}: 4%6=4
{9}: 9%6=3
{2}: 2%6=2
{4,9}: 13%6=1
{9,2}: 11%6=5 ← Max
{4,9,2}: 15%6=3

อัลกอริทึม (Prefix Sum + Ordered Set)

1. คำนวณ Prefix Sum Modulo: prefix[i] = (prefix[i-1] + arr[i]) % m
2. ใช้ Set (BST) เก็บ prefix sums ที่ผ่านมา
3. สำหรับแต่ละ prefix[i]:
   • maxSumMod = max(maxSumMod, prefix[i])
   • หา lower_bound(prefix[i] + 1) ใน set
   • ถ้ามี: maxSumMod = max(maxSumMod, prefix[i] - *it + m)
   • insert prefix[i] เข้า set

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

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

int calcMaxSum(int arr[], int n, int m) {
    int prefix = 0, maxSumMod = 0;
    set<int> sums;
    sums.insert(0);
    for (int i = 0; i < n; i++){
        prefix = (prefix + arr[i]) % m;
        maxSumMod = max(maxSumMod, prefix);
        auto it = sums.lower_bound(prefix + 1);
        if (it != sums.end())
            maxSumMod = max(maxSumMod, prefix - (*it) + m);
        sums.insert(prefix);
    }
    return maxSumMod;
}

int main() {
    int arr[] = {4, 9, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int m = 5;
    cout << "Maximum subarray sum modulo " << m << " is " << calcMaxSum(arr, n, m) < endl;
    return 0;
}

ผลลัพธ์

Maximum subarray sum modulo 5 is 4