C++ में K लगातार सब-ऐरे के न्यूनतम में अधिकतम को अधिकतम करना

दिया गया कार्य एक ऐरे arr[] को K लगातार सब-ऐरे में विभाजित करना और K लगातार सब-ऐरे के न्यूनतम में अधिकतम के अधिकतम संभव मान को ढूंढना है।

इनपुट

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

आउटपुट

9

व्याख्या - जो 3 लगातार सब-ऐरे बनाए जा सकते हैं: {2, 8, 4, 3}, {9}, और {1, 5}

इन सभी ऐरे से न्यूनतम मान हैं: (2, 9, 1)

इन तीनों में से अधिकतम मान 9 है।

इनपुट

arr[] = {8, 4, 1, 9, 11}, K=1

आउटपुट

11

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण

• यदि हम कार्य को देखें, तो इसे 3 मामलों में विभाजित किया जा सकता है - जब K=1, K=2 और K>=3।
• केस 1 - K=1: जब K=1 होता है तो सब-ऐरे ऐरे के बराबर होता है और इसलिए ऐरे में न्यूनतम मान आउटपुट होगा।
• केस 2 - K=2: यह एक कठिन मामला है। इस मामले में हमें दो ऐरे बनाने होंगे जिनमें प्रीफिक्स और सफिक्स न्यूनतम होंगे क्योंकि ऐरे को केवल 2 भागों में विभाजित किया जा सकता है। फिर ऐरे के प्रत्येक एलिमेंट के लिए हमें यह करना होगा - MaxValue = max(MaxValue, max(प्रीफिक्स न्यूनतम मान i पर, सफिक्स अधिकतम मान i+1 पर))
• केस 3 - K>=3: जब K>=3 होता है तो हम हमेशा ऐरे के अधिकतम एलिमेंट को एक अलग सब-ऐरे में रख सकते हैं, इसलिए उत्तर ऐरे का अधिकतम एलिमेंट होगा।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

/* K सब-ऐरे के न्यूनतम के अधिकतम के अधिकतम संभव मान को खोजने का फंक्शन */
int Max(const int* arr, int size, int K) {
    int MaxVal = INT_MIN;
    int MinVal = INT_MAX;
    
    // अधिकतम और न्यूनतम प्राप्त करें
    for (int i = 0; i < size; i++) {
        MinVal = min(MinVal, arr[i]);
        MaxVal = max(MaxVal, arr[i]);
    }
    
    // जब K=1, न्यूनतम मान रिटर्न करें
    if (K == 1) {
        return MinVal;
    }
    // जब K>=3, अधिकतम मान रिटर्न करें
    else if (K >= 3) {
        return MaxVal;
    }
    /* जब K=2 तब प्रीफिक्स और सफिक्स न्यूनतम बनाएं */
    else {
        // प्रीफिक्स और सफिक्स न्यूनतम संग्रहीत करने के लिए ऐरे
        vector<int> Left(size), Right(size);
        Left[0] = arr[0];
        Right[size - 1] = arr[size - 1];
        
        // प्रीफिक्स न्यूनतम
        for (int i = 1; i < size; i++) {
            Left[i] = min(Left[i - 1], arr[i]);
        }
        
        // सफिक्स न्यूनतम
        for (int i = size - 2; i >= 0; i--) {
            Right[i] = min(Right[i + 1], arr[i]);
        }
        
        int MaxValue = INT_MIN;
        // अधिकतम संभव मान प्राप्त करें
        for (int i = 0; i < size - 1; i++) {
            MaxValue = max(MaxValue, max(Left[i], Right[i + 1]));
        }
        return MaxValue;
    }
}

int main() {
    int arr[] = {9, 4, 12, 5, 6, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout << "Maximize the maximum among minimum of K consecutive sub-arrays is: " << Max(arr, size, K);
    return 0;
}

आउटपुट

Maximize the maximum among minimum of K consecutive sub-arrays is: 11