3018. Maximum Number of Removal Queries That Can Be Processed I

You are given a 0-indexed array nums and a 0-indexed array queries.

You can do the following operation at the beginning at most once:

• Replace nums with a subsequence of nums.

We start processing queries in the given order; for each query, we do the following:

• If the first and the last element of nums is less than queries[i], the processing of queries ends.
• Otherwise, we choose either the first or the last element of nums if it is greater than or equal to queries[i], and we remove the chosen element from nums.

Return the maximum number of queries that can be processed by doing the operation optimally.

class Solution {
public:
    int maximumProcessableQueries(vector<int>& A, vector<int>& Q) {
        int n = A.size(), m = Q.size();
        vector<vector<int>> dp(n,vector<int>(n));
        for(int i = 0; i < n; i++) for(int j = n - 1; j >= i; j--) {
            if(i > 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j]);
                if(dp[i-1][j] < m and A[i-1] >= Q[dp[i-1][j]]) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j] + 1);
                }
            }
            if(j + 1 < n) {
                dp[i][j] = max(dp[i][j], dp[i][j+1]);
                if(dp[i][j+1] < m and A[j+1] >= Q[dp[i][j+1]]) {
                    dp[i][j] = max(dp[i][j], dp[i][j+1] + 1);
                }
            }
            if(dp[i][j] == m) return m;
        }
        int res = 0;
        for(int i = 0; i < n; i++) res = max(res, dp[i][i] + (A[i] >= Q[dp[i][i]]));
        return res;
    }
};