इस समस्या में, हमें n पूर्णांकों का एक सरणी arr[] दिया गया है। हमारा काम उप-सरणी के अधिकतम आकार को खोजने के लिए एक प्रोग्राम बनाना है जो दी गई शर्त को पूरा करता है।
समस्या का विवरण - हमें सबसे बड़े सबअरे की लंबाई ज्ञात करनी होगी जो नीचे दी गई किसी भी शर्त को पूरा करती हो,
-
arr[k]> arr[k+1], यदि k विषम है और arr[k]
-
arr[k]
यहाँ, k, arr[] में उप-सरणी के तत्व का सूचकांक है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {7, 3, 1, 5, 4, 2, 9} आउटपुट
4
स्पष्टीकरण
The subarray {3, 1, 5, 4} satisfies the condition 1.
k = 1(odd), arr[k] > arr[k+1], 3 > 1
k = 2(even), arr[k] < arr[k+1], 1 < 5
k = 3(odd), arr[k] > arr[k+1], 5 > 4 समाधान दृष्टिकोण
हम उदाहरण से देख सकते हैं कि किसी भी शर्त के सत्य होने के लिए। उप-सरणी में वैकल्पिक बड़े-छोटे तत्व होने चाहिए, यानी यदि पहला> दूसरा, फिर दूसरा> तीसरा, और इसी तरह।
अब, गणना में आसानी के लिए, हम इस संबंध को दर्शाते हुए एक संबंध सरणी बनाएंगे। निम्नलिखित है कि हम संबंध सरणी को कैसे तैयार करेंगे,
If arr[i] == arr[i + 1],relArr[i] = ‘E’ If arr[i] > arr[i + 1],relArr[i] = ‘G’ If arr[i] < arr[i + 1],relArr[i] = ‘S’
इस सरणी का उपयोग करके हम आसानी से अधिकतम उपसरणी आकार पा सकते हैं। विचार किए जाने वाले सबरे में वैकल्पिक 'जी' और 'एस' होंगे।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include<iostream>
using namespace std;
char findRel(int a, int b) {
if(a > b)
return 'G';
else if(a < b)
return 'S';
return 'E';
}
int calcMaxSubArray(int arr[], int n) {
int maxLen = 1;
int len = 1;
char c = findRel(arr[0], arr[1]);
for(int i = 1; i <= n−1; i++){
if(c == 'S' && findRel(arr[i], arr[i + 1]) == 'G')
len++;
else if(c == 'G' && findRel(arr[i], arr[i + 1]) == 'S')
len++;
else {
if(maxLen < (len + 1))
maxLen = (len + 1);
len = 1;
}
c = findRel(arr[i], arr[i+1]);
}
return maxLen;
}
int main() {
int arr[] = {7, 3, 1, 5, 4, 2, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum size of sub−array that satisfies the given
condition is "<<calcMaxSubArray(arr, n);
} आउटपुट
The maximum size of sub-array that satisfies the given condition is 4