इस समस्या में, हमें n आकार का एक सरणी arr[] दिया जाता है जिसमें धनात्मक मान होते हैं। हमारा काम अधिकतम योग उप-सरणी खोजने के लिए एक प्रोग्राम बनाना है, जैसे कि प्रारंभ और समाप्ति मान समान हैं।
समस्या का विवरण - यहां, हमें एक सबएरे को खोजने की जरूरत है, जैसे कि इंडेक्स i (सबअरे का शुरुआती इंडेक्स) और जे (सबअरे का इंडेक्स इंडेक्स) एक ही है यानी एआर [i] =एआर [जे]। और उपसरणी के तत्वों का योग अधिकतम होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
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 समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें इस तथ्य पर विचार करने की आवश्यकता है कि सकारात्मक मूल्यों के लिए उप-सरणियों का योग हमारे द्वारा विचार किए गए उप-सरणियों के आकार के साथ बढ़ता है। इसके लिए, हम सरणी में संख्याओं की सबसे बाईं और दाईं ओर की घटना को ढूंढकर अधिकतम आकार के साथ उप-सरणी पाएंगे। और अगर यह मैक्ससम से अधिक है तो उनकी राशि वापस कर दें।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#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