C++ में k को अधिकतम तत्व मानने वाले गैर-अतिव्यापी उपसरणियों की लंबाई का अधिकतम योग (Maximum sum of lengths of non-overlapping subarrays with k as the max element)

इस समस्या में, हमें एक सरणी और एक पूर्णांक k दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में k को अधिकतम तत्व मानने वाले गैर-अतिव्यापी उपसरणियों की लंबाई का अधिकतम योग ढूंढे।

समस्या विवरण - यहां, हमारे पास एक सरणी और एक पूर्णांक k है। हमें इस सरणी से बनने वाले सभी संभावित गैर-अतिव्यापी उप-सरणियों को ढूंढना है। और बनाई गई सभी उपसरणियों की लंबाई का योग करना है।

आइए एक उदाहरण से समझते हैं:

इनपुट - सरणी = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5} k = 3

आउटपुट - 7

व्याख्या - अधिकतम तत्व 3 वाली गैर-अतिव्यापी उपसरणियां:

{3} : लंबाई = 1
{1, 2, 3, 1} : लंबाई = 4
{3, 2} : लंबाई = 2
लंबाई का योग = 1+4+2 = 7

इस समस्या को हल करने के लिए, हम सरणी को पार करेंगे और उन सभी तत्वों को ढूंढेंगे जो k से कम या बराबर हैं और एक लंबाई बनाए रखेंगे, यदि उपसरणी (तत्वों की धारा) में k है तो लंबाई को योग में जोड़ें।

उदाहरण

#include <iostream>
using namespace std;

int subArrayLengthSum(int arr[], int n, int k){
    int lengthSum = 0;
    int subarrayLength = 0;
    int flag = 0;
    for (int i = 0; i < n;) {
        subarrayLength = 0;
        flag = 0;
        while (arr[i] <= k && i < n) {
            subarrayLength++;
            if (arr[i] == k)
                flag = 1;
            i++;
        }
        if (flag == 1)
            lengthSum += subarrayLength;
        while (arr[i] > k && i < n)
            i++;
    }
    return lengthSum;
}

int main(){
    int arr[] = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int ans = subArrayLengthSum(arr, size, k);
    cout << "अधिकतम तत्व " << k << " के साथ गैर-अतिव्यापी उपसरणियों की लंबाई का अधिकतम योग है " << ans;
    return 0;
}

आउटपुट

अधिकतम तत्व 3 के साथ गैर-अतिव्यापी उपसरणियों की लंबाई का अधिकतम योग है 7