C++-এ শুরু ও শেষ মান একই হয় এমন সর্বোচ্চ সম সাবঅ্যারে বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি ইন্টিজার অ্যারে দেওয়া থাকলে, এমন সাবঅ্যারে খুঁজে বের করতে হবে যেটির শুরু এবং শেষ মান একই হয় এবং এর সম সর্বোচ্চ হয়।

সমাধানের পদ্ধতি

1. প্রতিটি ভ্যালুর প্রথম ও শেষ উপস্থিতির ইন্ডেক্স সংরক্ষণ করুন (first, last ম্যাপ)।
2. প্রিফিক্স সম অ্যারে pr[] বানান।
3. প্রতিটি ইন্ডেক্স i এর জন্য, ভ্যালু a[i] এর প্রথম ও শেষ ইন্ডেক্স নিন।
4. সাবঅ্যারে সম = pr[last] - pr[first-1]।
5. সর্বোচ্চ সম আপডেট করুন।

C++ কোড উদাহরণ

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

int maxValue(int a[], int n) {
    unordered_map first, last;
    int pr[n];
    pr[0] = a[0];
    for (int i = 1; i < n; i++) {
        pr[i] = pr[i - 1] + a[i];
        if (first[a[i]] == 0) first[a[i]] = i;
        last[a[i]] = i;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int start = first[a[i]];
        int end = last[a[i]];
        ans = max(ans, pr[end] - (start > 0 ? pr[start - 1] : 0));
    }
    return ans;
}

int main() {
    int arr[] = {1, 3, 5, 2, 4, 18, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxValue(arr, n);
    return 0;
}

আউটপুট

37

জটিলতা

• সময়: O(n)
• স্থান: O(n)