এই সমস্যায়, আমাদেরকে ইতিবাচক মান নিয়ে গঠিত n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে সর্বাধিক যোগফল সাব্যারে পাওয়া যায় যেমন শুরু এবং শেষের মান একই।
সমস্যা বর্ণনা − এখানে, আমাদের এমন একটি সাবঅ্যারে খুঁজে বের করতে হবে যাতে সূচী i (সাবয়ারের শুরুর সূচী) এবং j (সাবয়ারের শেষ সূচক) এর উপাদানগুলি একই হয় যেমন arr[i] =arr[j]। এবং সাবয়ারের উপাদানগুলির যোগফল সর্বাধিক করা হয়৷
৷সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {2, 1, 3, 5, 6, 2, 4, 3} আউটপুট
23
ব্যাখ্যা
All subarrays which are starting and ending with the same element are:
{2, 1, 3, 5, 6, 2} = 2 + 1 + 3 + 5 + 6 + 2 = 19
{3, 5, 6, 2, 4, 3} = 3 + 5 + 6 + 2 + 4 + 3 = 23 সমাধান পদ্ধতি
সমস্যাটি সমাধান করার জন্য, আমাদের এই বিষয়টি বিবেচনা করতে হবে যে ধনাত্মক মানগুলির জন্য আমরা যে সাব্যারেগুলির আকার বিবেচনা করি তার সাথে সাবরেরের যোগফল বৃদ্ধি পায়। এর জন্য, আমরা অ্যারের মধ্যে সংখ্যার বামদিকের ডানদিকের উপস্থিতি খুঁজে বের করার মাধ্যমে সর্বাধিক আকার সহ সাবঅ্যারেটি খুঁজে পাব। এবং maxSum এর থেকে বেশি হলে তাদের যোগফল ফেরত দিন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#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[arr[i]] == 0)
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] − sumArr[left − 1]);
}
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
