C++-এ ম্যাক্সিমাম সাবঅ্যারে সাম মডুলো m

একটি অ্যারে (সাইজ n) এবং একটি ইন্টিজার m দেওয়া আছে। সব সাবঅ্যারের সাম মডুলো m-এর ম্যাক্সিমাম মান বের করতে হবে।

উদাহরণ: array = {4, 9, 2}, m = 6 -> আউটপুট: ৫

ব্যাখ্যা: সাবঅ্যারে ও তাদের রিমেইন্ডার: {4}: 4%6=4, {9}: 9%6=3, {2}: 2%6=2 {4,9}: 13%6=1, {9,2}: 11%6=5, {4,9,2}: 15%6=3 ম্যাক্সিমাম = ৫

সমাধান: প্রিফিক্স সাম মডুলো অ্যারে কম্পিউট করব। সেট (set) ব্যবহার করে প্রতিটি ইনডেক্সে maxSum = max(maxSum, (prefix_i - prefix_j + m) % m) ক্যালকুলেট করব।

উদাহরণ

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

int calcMaxSum(int arr[], int n, int m) {
    int x, 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