সি++-এ একই শুরু ও শেষ মান دار সর্বোচ্চ যোগফল সাবঅ্যারে বের করা

সমস্যা বিবরণ

একটি পজিটিভ অ্যারে arr[] দেওয়া আছে। এমন সাবঅ্যারে খুঁজে বের করতে হবে যাতে শুরু এবং শেষ উপাদান একই হয় এবং যোগফল সর্বোচ্চ হয়।

উদাহরণ: arr = {2,1,3,5,6,2,4,3} → আউটপুট 23। সাবঅ্যারে: [3,5,6,2,4,3] (শুরু ৩, শেষ ৩, যোগফল ২৩)।

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

প্রিফিক্স সাম + হ্যাশ ম্যাপ (প্রথম ও শেষ ইনডেক্স ট্র্যাক):

1. startIndex[val] = মান val-এর প্রথম আপিরেন্স।
2. endIndex[val] = মান val-এর শেষ আপিরেন্স।
3. sumArr[i] = প্রিফিক্স সাম।
4. প্রতিটি উপাদানের জন্য left = startIndex[arr[i]], right = endIndex[arr[i]]।
5. সাবঅ্যারে যোগফল = sumArr[right] - sumArr[left-1]।
6. সর্বোচ্চ মান আপডেট করুন।

উদাহরণ কোড

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

int maxValue(int arr[], int n) {
    unordered_map<int, int> startIndex, endIndex;
    int sumArr[n];
    sumArr[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sumArr[i] = sumArr[i-1] + arr[i];
        if (!startIndex.count(arr[i])) startIndex[arr[i]] = i;
        endIndex[arr[i]] = i;
    }
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        int left = startIndex[arr[i]];
        int right = endIndex[arr[i]];
        maxSum = max(maxSum, sumArr[right] - (left > 0 ? sumArr[left-1] : 0));
    }
    return maxSum;
}

int main() {
    int arr[] = {2, 1, 3, 5, 6, 2, 4, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "The maximum sum subarray such that start and end values are same is " << maxValue(arr, n);
    return 0;
}

আউটপুট

The maximum sum subarray such that start and end values are same is 23