C++ प्रोग्राम में दी गई शर्त को पूरा करने वाले उप-सरणी का अधिकतम आकार

इस समस्या में, हमें n पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो दी गई शर्त को पूरा करने वाले उप-सरणी का अधिकतम आकार ढूंढे।

समस्या विवरण

हमें सबसे बड़ी उपसरणी की लंबाई ढूंढनी है जो नीचे दी गई किसी एक शर्त को पूरा करती हो,

• यदि k विषम है तो arr[k] > arr[k+1] और यदि k सम है तो arr[k] < arr[k+1]। उपसरणी के सभी तत्वों के लिए।
• यदि k विषम है तो arr[k] < arr[k+1] और यदि k सम है तो arr[k] > arr[k+1]। उपसरणी के सभी तत्वों के लिए।

यहां, k सरणी में उपसरणी के तत्व का सूचकांक है।

उदाहरण

इनपुट

arr[] = {7, 3, 1, 5, 4, 2, 9}

आउटपुट

4

व्याख्या

उपसरणी {3, 1, 5, 4} शर्त 1 को पूरा करती है। 
k = 1(विषम), arr[k] > arr[k+1], 3 > 1 
k = 2(सम), arr[k] < arr[k+1], 1 < 5 
k = 3(विषम), arr[k] > arr[k+1], 5 > 4

समाधान दृष्टिकोण

हम उदाहरण से देख सकते हैं कि किसी भी शर्त के सत्य होने के लिए। उपसरणी में वैकल्पिक बड़े-छोटे तत्व होने चाहिए यानी यदि पहला > दूसरा, तो दूसरा > तीसरा, और इसी तरह।

अब, गणना में आसानी के लिए, हम एक संबंध सरणी बनाएंगे जो इस संबंध को दर्शाती है। निम्नलिखित वह तरीका है जिससे हम संबंध सरणी को तैयार करेंगे,

यदि arr[i] == arr[i + 1], relArr[i] = 'E' 
यदि arr[i] > arr[i + 1], relArr[i] = 'G' 
यदि arr[i] < arr[i + 1], relArr[i] = 'S'

इस सरणी का उपयोग करके हम आसानी से अधिकतम उपसरणी आकार ढूंढ सकते हैं। विचार की जाने वाली उपसरणी में वैकल्पिक 'G' और '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