C++ में अधिकतम तत्व के रूप में k के साथ गैर-अतिव्यापी उपसरणियों की लंबाई का अधिकतम योग

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

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

समस्या को समझने के लिए एक उदाहरण लेते हैं,

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

आउटपुट - 7

स्पष्टीकरण - अधिकतम तत्व 3 के साथ गैर-अतिव्यापी उप-सरणी:

{3} : length = 1
{1, 2, 3, 1} : length = 4
{3, 2} : length = 2
Sum of length = 1+4+2 = 7

इस समस्या को हल करने के लिए, हम सरणी को पार करेंगे और सभी तत्वों को कम करेंगे और लंबाई बनाए रखेंगे, यदि सबरे (तत्वों की धारा) में 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<<"The max sum of lengths of non-overlapping subarrays with "<<k<<" as max element is "<<ans;
   return 0;
}

आउटपुट

The max sum of lengths of non-overlapping subarrays with 3 as max element is 7