इस समस्या में, हमें एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो सरणी में सबसे छोटे और दूसरे सबसे छोटे तत्व का अधिकतम योग ढूंढे।
समस्या विवरण
हमें सरणी के एक उपसरणी (subarray) के सबसे छोटे और दूसरे सबसे छोटे तत्वों का योग ढूंढना है। और ऐसे सभी उपसरणी योगों में से अधिकतम वापस करना है।
उदाहरण
इनपुट
arr[] = {3, 5, 4, 2, 9, 1, 6}
आउटपुट
11
व्याख्या
सभी संभावित उपसरणियों में से, {2, 9} में सबसे छोटे तत्वों का अधिकतम योग है। योग = 2 + 9 = 11
समाधान दृष्टिकोण
समस्या का एक सरल समाधान सभी उपसरणियाँ उत्पन्न करना है। सबसे छोटे और दूसरे सबसे छोटे तत्व ढूंढना, उनका योग निकालना। सभी में से अधिकतम योग वापस करना।
एक अधिक कुशल समाधान उदाहरणों के अवलोकन पर आधारित है। हमें अधिकतम योग ढूंढना है जो सरणी के दो लगातार तत्व जोड़े का योग होगा। और हम अधिकतम योग वाले जोड़े को ढूंढेंगे।
एल्गोरिदम
आरंभीकरण -
maxSum = -1
चरण 1 -
लूप i → 0 से n-1 तक
चरण 1.1 -
यदि maxSum < (arr[i] + arr[i+1])। तब, maxSum = (arr[i] + arr[i+1])
चरण 2 -
maxSum वापस करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <iostream>
using namespace std;
int calcMaxSumPairs(int arr[], int n) {
int maxSum = -1;
for (int i=0; i< (n - 1); i++)
if(maxSum < (arr[i] + arr[i + 1]))
maxSum = (arr[i] + arr[i + 1]);
return maxSum;
}
int main() {
int arr[] = {3, 4, 2, 9, 5, 6};
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum sum of smallest and second smallest in an array is "<<calcMaxSumPairs(arr, n);
return 0;
}
आउटपुट
The maximum sum of smallest and second smallest in an array is 14