จำนวนย่อยอาร์เรย์ที่ค่าสูงสุดอยู่ในช่วงใน C++

ให้อาร์เรย์ A ของจำนวนเต็มบวก และขอบเขต L, R ต้องการนับจำนวนย่อยอาร์เรย์ (contiguous, non-empty) ที่ค่าสูงสุด (maximum) อยู่ในช่วง [L, R]

ตัวอย่าง: A=[2,1,4,3], L=2, R=3 → 3 (ย่อยอาร์เรย์คือ [2], [2,1], [3])

ขั้นตอนการแก้ปัญหา (DP แบบ O(N))

1. ret = 0, dp = 0, prev = -1 (prev = ตำแหน่งล่าสุดที่ A[i] > R)
2. วน i = 0..n-1:
   • ถ้า A[i] < L && i > 0 → ret += dp (ขยายย่อยอาร์เรย์เดิม)
   • ถ้า A[i] > R → prev = i, dp = 0 (รีเซ็ต)
   • ถ้า → dp = i - prev, ret += dp (เริ่มย่อยอาร์เรย์ใหม่หรือต่อยอด)
3. คืน ret

ไอเดีย: dp = จำนวนย่อยอาร์เรย์ที่ลงท้ายที่ i และ max อยู่ในช่วง

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int ret = 0, dp = 0, 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;
    }
};

int 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