จำนวน Subarrays ที่มีขอบเขตสูงสุดใน C++

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็มบวก และจำนวนเต็มบวกสองจำนวน L และ R ก็จะได้รับเช่นกัน เราต้องหาจำนวนของอาร์เรย์ย่อย (ต่อเนื่องกัน ไม่ว่าง) เพื่อให้ค่าขององค์ประกอบอาร์เรย์สูงสุดในอาร์เรย์ย่อยนั้นมีค่าอย่างน้อย L และมากที่สุด R ดังนั้นถ้า A =[2,1,4,3] และ L =2 และ R =3 จากนั้นเอาต์พุตจะเป็น 3 เนื่องจากมีอาร์เรย์ย่อยสามชุดที่ตรงตามข้อกำหนด ดังนั้นนี่คือ [2], [2,1], [3].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret :=0, dp :=0, ก่อนหน้า :=-1

• สำหรับผมอยู่ในช่วง 0 ถึงขนาด A – 1

  • ถ้า A[i] 0 แล้ว ret :=ret + dp

  • ถ้า A[i]> R แล้ว prev :=i และ dp :=0

  • มิฉะนั้นเมื่อ A[i]>=L และ A[i] <=R จากนั้น dp :=i – prev and 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