দেওয়া শর্ত পূরণকারী সর্বোচ্চ সাব-অ্যারে আকার (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n সংখ্যক পূর্ণসংখ্যা সহ একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল দেওয়া শর্ত পূরণকারী সর্বোচ্চ সাব-অ্যারে আকার খুঁজে বের করার প্রোগ্রাম তৈরি করা।

আমাদের সাবঅ্যারের সর্বোচ্চ দৈর্ঘ্য বের করতে হবে যা নিচের যেকোনো একটি শর্ত পূরণ করে:

• arr[k] > arr[k+1], যদি k বিজোড় হয় এবং arr[k] < arr[k+1], যদি k জোড় হয়। সাবঅ্যারের সব উপাদানের জন্য।
• arr[k] < arr[k+1], যদি k বিজোড় হয় এবং arr[k] > arr[k+1], যদি k জোড় হয়। সাবঅ্যারের সব উপাদানের জন্য।

এখানে, k হল arr[]-এ সাবঅ্যারের উপাদানের ইনডেক্স।

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

4

সাবঅ্যারে {3, 1, 5, 4} শর্ত ১ পূরণ করে।
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 
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);
    return 0;
}

The maximum size of sub-array that satisfies the given condition is 4