इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जिसमें सबसे बड़े सबअरे का योग k से अधिक होता है।
आइए समस्या को हल करने के लिए चरणों को देखें।
- सरणी प्रारंभ करें।
- सरणी पर पुनरावृति करें और अनुक्रमणिका के साथ वेक्टर में प्रत्येक अनुक्रमणिका पर योग संग्रहीत करें।
- उपरोक्त राशियों को योग और अनुक्रमणिका के आधार पर क्रमबद्ध करें।
- इंडेक्स को स्टोर करने के लिए ऐरे को इनिशियलाइज़ करें।
- एक लूप लिखें जो n तक पुनरावृत्त हो।
- उपरोक्त अनुक्रमणिका सरणी के न्यूनतम अनुक्रमणिका और पिछले योग सरणी अनुक्रमणिका वाले मानों को अद्यतन करें।
- योग को 0 से प्रारंभ करें।
- एक लूप लिखें जो n तक पुनरावृत्त हो।
- योग में वर्तमान तत्व जोड़ें।
- यदि योग k से अधिक है।
- अधिकतम उपसरणी लंबाई i + 1 है।
- अन्यथा अधिकतम उपसरणी लंबाई है
- बाइनरी खोज का उपयोग करके पिछले योगों से अनुक्रमणिका खोजें।
- योग जो योग - k - 1 से कम है, वह तत्व सूचकांक है जो हम चाहते हैं।
उदाहरण
आइए कोड देखें।
#include <bits/stdc++.h>
using namespace std;
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
if (a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
int findIndex(vector<pair<int, int> >& previousSums, int n, int val) {
int start = 0;
int end = n - 1;
int mid, result = -1;
while (start <= end) {
mid = (start + end) / 2;
if (previousSums[mid].first <= val) {
result = mid;
start = mid + 1;
}else {
end = mid - 1;
}
}
return result;
}
int getLargestSubArray(int arr[], int n, int k) {
int maxLength = 0;
vector<pair<int, int> > previousSums;
int sum = 0, minIndexes[n];
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
previousSums.push_back({ sum, i });
}
sort(previousSums.begin(), previousSums.end(), compare);
minIndexes[0] = previousSums[0].second;
for (int i = 1; i < n; i++) {
minIndexes[i] = min(minIndexes[i - 1], previousSums[i].second);
}
sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
if (sum > k) {
maxLength = i + 1;
}else {
int ind = findIndex(previousSums, n, sum - k - 1);
if (ind != -1 && minIndexes[ind] < i) {
maxLength = max(maxLength, i - minIndexes[ind]);
}
}
}
return maxLength;
}
int main() {
int arr[] = { 5, 3, -3, 2, 4, 7 };
int k = 5, n = 6;
cout << getLargestSubArray(arr, n, k) << endl;
return 0;
} आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।
6
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उनका टिप्पणी अनुभाग में उल्लेख करें।