C++에서 최대 경계가 있는 부분배열의 수

양의 정수로 구성된 배열 A가 있고 두 개의 양의 정수 L과 R도 주어진다고 가정합니다. 우리는 그 하위 배열의 최대 배열 요소의 값이 최소 L과 최대 R이 되도록 (인접한, 비어 있지 않은) 하위 배열의 수를 찾아야 합니다. 따라서 A =[2,1,4,3]이고 L =2 및 R =3이면 요구 사항을 충족하는 3개의 하위 배열이 있으므로 출력은 3이 됩니다. [2], [2,1], [3]입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret :=0, dp :=0, 이전 :=-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

• 리턴 렛

예시(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