C++ में सीमित अधिकतम के साथ उपसरणी की संख्या

मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी A है, और दो धनात्मक पूर्णांक L और R भी दिए गए हैं। हमें (सन्निकट, गैर-खाली) उपसरणी की संख्या ढूंढनी है जैसे कि उस उपसरणी में अधिकतम सरणी तत्व का मान कम से कम L और अधिकतम R हो।

उदाहरण के लिए, यदि A = [2,1,4,3] और L = 2 और R = 3, तो आउटपुट 3 होगा क्योंकि तीन उपसरणी हैं जो आवश्यकताओं को पूरा करती हैं। ये हैं [2], [2,1], [3]।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

ret := 0, dp := 0, prev := -1
i को 0 से A के आकार - 1 तक लूप करें
- यदि A[i] < L और i > 0, तो ret := ret + dp
- यदि A[i] > R, तो prev := i और dp := 0
- अन्यथा जब A[i] >= L और A[i] <= R, तो dp := i - prev और ret := ret + dp
ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {       int ret = 0;       int dp = 0;       int prev = -1;       for(int i = 0; i < A.size(); i++){          if(A[i] < L && i > 0){             ret += dp;          }          if(A[i] > R){             prev = i;             dp = 0;          }          else if(A[i] >= L && A[i] <= R){             dp = i - prev;             ret += dp;          }       }       return ret;    } }; main(){    vector<int> v = {2,1,4,3};    Solution ob;    cout << (ob.numSubarrayBoundedMax(v, 2, 3)); }

इनपुट

[2,1,4,3] 2 3