Number of Subarrays with Bounded Maximum in C++

Suppose we have an array A of positive integers, and two positive integers L and R are also given. We have to find the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R. So if A = [2,1,4,3] and L = 2 and R = 3, then output will be 3 as there are three sub arrays that meet the requirements. So these are [2], [2,1], [3].

To solve this, we will follow these steps −

• ret := 0, dp := 0, prev := -1

• for i in range 0 to size of A – 1

  • if A[i] < L and i > 0, then ret := ret + dp

  • if A[i] > R, then prev := i and dp := 0

  • otherwise when A[i] >= L and A[i] <= R, then dp := i – prev and ret := ret + dp

• return ret

Example (C++)

Let us see the following implementation to get better understanding −

 Live Demo

#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)); }

Input

[2,1,4,3] 2 3

Output

3