इस समस्या में, हमें एक सरणी और एक योग दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में दिए गए योग से कम या बराबर योग वाली अधिकतम योग उपसरणी ढूंढे।
हमें किसी भी लंबाई की उपसरणी ढूंढनी है जिसका योग दिए गए योग से कम या बराबर हो।
आइए एक उदाहरण से समझते हैं:
इनपुट - सरणी = {3, 5, 1, 8, 2, 9}, योग = 25
आउटपुट - 25
व्याख्या - योग 25 से कम या बराबर वाली उपसरणियां हैं {5, 1, 8, 2, 9}
अधिकतम योग उपसरणी ढूंढने की एक सरल विधि सरणी पर पुनरावृति करना और सभी उपसरणियों का योग ढूंढना और फिर निकटतम या बराबर योग ढूंढना है। लेकिन इस विधि की समय जटिलता O(n²) होगी क्योंकि दो लूप आवश्यक हैं।
इस समस्या को हल करने की एक अधिक कुशल विधि स्लाइडिंग विंडो (sliding window) विधि है। जिसमें हम वर्तमान योग की तुलना अधिकतम योग से करेंगे और तुलना के आधार पर विंडो में तत्व जोड़ेंगे या घटाएंगे।
उदाहरण
#include <iostream>
using namespace std;
int findMax(int a, int b){
if(a > b) return a;
return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
int sum = arr[0], overallMax = 0, start = 0;
for (int i = 1; i < n; i++) {
if (sum <= maxSum)
overallMax = findMax(overallMax, sum);
while (sum + arr[i] > maxSum && start < i) {
sum -= arr[start];
start++;
}
sum += arr[i];
}
if (sum <= maxSum)
overallMax = findMax(overallMax, sum);
return overallMax;
}
int main(){
int arr[] = {3, 1, 4, 7, 2, 9, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 20;
cout << "अधिकतम योग वाली उपसरणी जिसका योग " << sum << " से कम या बराबर है: " << maxSumsubarray(arr, n, sum);
return 0;
}
आउटपुट
अधिकतम योग वाली उपसरणी जिसका योग 20 से कम या बराबर है: 18