समस्या विवरण
इस समस्या में, हमें आकार n का एक ऐरे arr[] दिया गया है जिसमें धनात्मक मान होते हैं। हमारा कार्य ऐसा प्रोग्राम बनाना है जो शुरुआत और अंत मान समान होने पर अधिकतम योग सबऐरे ढूंढे।
समस्या विवरण - यहां, हमें एक सबऐरे ढूंढना है जैसे कि इंडेक्स i (सबऐरे का शुरुआती इंडेक्स) और j (सबऐरे का अंतिम इंडेक्स) पर तत्व समान हों यानी arr[i] = arr[j]। और सबऐरे के तत्वों का योग अधिकतम हो।
उदाहरण
arr[] = {2, 1, 3, 5, 6, 2, 4, 3}
आउटपुट
23
व्याख्या
सभी सबऐरे जो समान तत्व से शुरू और खत्म होते हैं:
{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] - (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
