अधिकतम तत्व k से बड़ा होने वाली उप-सरणियों की गणना - C++

समस्या विवरण

हमें एक पूर्णांक ऐरे arr[] और एक चर k दिया गया है। लक्ष्य उन उप-सरणियों की गणना करना है जिनका अधिकतम तत्व k से बड़ा है।

उदाहरण

इनपुट: arr[] = {1,2,5,3}, k=3

आउटपुट: 6

व्याख्या: 5 वाली उप-सरणियाँ: [5], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]

इनपुट: arr[] = {1,2,3,4,5}, k=4

आउटपुट: 5

व्याख्या: केवल 5 वाली उप-सरणियाँ: [5], [4,5], [3,4,5], [2,3,4,5], [1,2,3,4,5]

दृष्टिकोण

कुल उप-सरणियाँ = n*(n+1)/2। उन उप-सरणियों को घटाएँ जिनके सभी तत्व k से छोटे या बराबर हैं। k से बड़े तत्वों को छोड़कर, लगातार k से छोटे तत्वों के खंडों की लंबाई l के लिए l*(l+1)/2 उप-सरणियाँ बनती हैं।

एल्गोरिदम

1. प्रारंभिक count = 0
2. i = 0 से size तक लूप करें:
   • यदि arr[i] > k तो छोड़ दें
   • अन्यथा आंतरिक लूप से temp = लगातार k से छोटे तत्वों की लंबाई गिनें
   • count += temp*(temp+1)/2
3. count = total_subarrays - count
4. count लौटाएँ

C++ कार्यान्वयन

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

int maximum_k(int arr[], int size, int k) {
    int count = 0;
    int i = 0;
    while (i < size) {
        if (arr[i] > k) { i++; continue; }
        int temp = 0;
        while (i < size && arr[i] <= k) { i++; temp++; }
        count += temp * (temp + 1) / 2;
    }
    count = (size * (size + 1) / 2) - count;
    return count;
}

int main() {
    int arr[] = {4, 1, 2, 7, 8, 3};
    int k = 5;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << maximum_k(arr, size, k);
    return 0;
}

आउटपुट

Count: 14