C++で最大値が制限されているサブアレイの数

正の整数の配列Aがあり、2つの正の整数LとRも指定されているとします。 （連続した、空でない）サブ配列の数を見つけて、そのサブ配列の最大配列要素の値が少なくともL、最大でRになるようにする必要があります。したがって、A =[2,1,4,3]であり、 L=2およびR=3の場合、要件を満たすサブアレイが3つあるため、出力は3になります。つまり、これらは[2]、[2,1]、[3]です。

これを解決するには、次の手順に従います-

• ret：=0、dp：=0、prev：=-1

• 0からA–1のサイズまでの範囲のiの場合

  • A [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

出力

3