Số lượng mảng con có giới hạn tối đa trong C ++

Giả sử chúng ta có một mảng A gồm các số nguyên dương và hai số nguyên dương L và R cũng được cho trước. Chúng ta phải tìm số lượng mảng con (liền nhau, không rỗng) sao cho giá trị của phần tử mảng lớn nhất trong mảng con đó ít nhất là L và nhiều nhất là R. Vì vậy, nếu A =[2,1,4,3] và L =2 và R =3, thì đầu ra sẽ là 3 vì có ba mảng con đáp ứng yêu cầu. Vì vậy, đây là [2], [2,1], [3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0, dp:=0, trước:=-1

• cho tôi trong phạm vi từ 0 đến kích thước của A - 1

  • nếu A [i] 0, thì ret:=ret + dp

  • nếu A [i]> R, thì từ trước:=i và dp:=0

  • ngược lại khi A [i]> =L và A [i] <=R, thì dp:=i - prev và ret:=ret + dp

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

[2,1,4,3]
2
3

Đầu ra

3