2334. Subarray With Elements Greater Than Varying Threshold

You are given an integer array nums and an integer threshold.

Find any subarray of nums of length k such that every element in the subarray is greater than threshold / k.

Return the size of any such subarray. If there is no such subarray, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

class Solution {
public:
    int validSubarraySize(vector<int>& A, int k) {
        int n = A.size();
        vector<int> dp(n);
        priority_queue<pair<int, int>> q;
        for(int i = 0; i < n; i++) q.push({A[i],i});
        int ma = 0;
        for(int res = 1; res <= n; res++) {
            double target = 1.0 * k / res;
            while(!q.empty() and q.top().first > target) {
                auto [_, idx] = q.top(); q.pop();
                dp[idx] += 1;
                if(idx and dp[idx-1] and idx + 1 < n and dp[idx+1]) {
                    int left = dp[idx-1];
                    int right = dp[idx+1];
                    int sum = left + right + 1;
                    dp[idx-left] = dp[idx+right] = dp[idx] = sum;
                } else if(idx and dp[idx-1]) {
                    int left = dp[idx-1];
                    dp[idx] = dp[idx-left] = left + 1;
                } else if(idx + 1 < n and dp[idx+1]) {
                    int right = dp[idx+1];
                    dp[idx] = dp[idx + right] = right + 1;
                }

                ma = max(ma, dp[idx]);
                if(ma >= res) return res;
            }
            if(ma >= res) return res;
        }
        return -1;
    }
};