সি++-এ K চেয়ে বড় যোগফল বিশিষ্ট সর্ববৃহৎ সাবঅ্যারে

একটি অ্যারে এবং সংখ্যা k দেওয়া থাকলে, যোগফল k চেয়ে বড় এমন সর্বোচ্চ দৈর্ঘ্যের সাবঅ্যারে বের করতে হবে।

অ্যালগরিদম

• প্রিফিক্স সম এবং ইনডেক্স ভেক্টরে রাখুন।
• সামান্য সময় সর্ট করুন (সম এবং ইনডেক্স অনুযায়ী)।
• minIndex অ্যারে বানান।
• প্রতিটি ইনডেক্সের জন্য বাইনারি সার্চ দিয়ে sum - k - 1 চেয়ে ছোট প্রিফিক্স খুঁজুন।
• সর্বোচ্চ দৈর্ঘ্য আপডেট করুন।

সি++ ইমপ্লিমেন্টেশন

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

bool compare(const pair& a, const pair& b) {
    if (a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

int findIndex(vector>& pref, int n, int val) {
    int l = 0, r = n - 1, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (pref[mid].first <= val) { ans = mid; l = mid + 1; }
        else r = mid - 1;
    }
    return ans;
}

int getLargestSubarray(int arr[], int n, int k) {
    vector> pref;
    int sum = 0, minIdx[n];
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        pref.push_back({sum, i});
    }
    sort(pref.begin(), pref.end(), compare);
    minIdx[0] = pref[0].second;
    for (int i = 1; i < n; i++) minIdx[i] = min(minIdx[i-1], pref[i].second);
    sum = 0;
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum > k) maxLen = i + 1;
        else {
            int idx = findIndex(pref, n, sum - k - 1);
            if (idx != -1 && minIdx[idx] < i)
                maxLen = max(maxLen, i - minIdx[idx]);
        }
    }
    return maxLen;
}

int main() {
    int arr[] = {5, 3, -3, 2, 4, 7};
    int k = 5, n = 6;
    cout << getLargestSubarray(arr, n, k) << endl; // 6
    return 0;
}

আউটপুট

6