Skip to content

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

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int maximumProcessableQueries(vector<int>& nums, vector<int>& queries) {
    const int n = nums.size();
    int ans = 0;
    // dp[i][j] := the maximum number of queries processed if nums[i..j] are not
    // removed after processing dp[i][j] queries
    vector<vector<int>> dp(n, vector<int>(n));

    for (int d = n - 1; d >= 0; --d) {
      for (int i = 0; i < n; ++i) {
        const int j = i + d;
        if (j >= n)
          continue;
        if (i > 0)
          // Remove nums[i - 1] from nums[i - 1..j] if possible.
          dp[i][j] = max(dp[i][j],
                         dp[i - 1][j] + (nums[i - 1] >= queries[dp[i - 1][j]]));
        if (j + 1 < n)
          // Remove nums[j + 1] from nums[i..j + 1] if possible.
          dp[i][j] = max(dp[i][j],
                         dp[i][j + 1] + (nums[j + 1] >= queries[dp[i][j + 1]]));
        if (dp[i][j] == queries.size())
          return queries.size();
      }
    }

    for (int i = 0; i < n; ++i)
      ans = max(ans, dp[i][i] + (nums[i] >= queries[dp[i][i]]));

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int maximumProcessableQueries(int[] nums, int[] queries) {
    final int n = nums.length;
    int ans = 0;
    // dp[i][j] := the maximum number of queries processed if nums[i..j] are not
    // removed after processing dp[i][j] queries
    int[][] dp = new int[n][n];

    for (int d = n - 1; d >= 0; --d) {
      for (int i = 0; i < n; ++i) {
        final int j = i + d;
        if (j >= n)
          continue;
        if (i > 0)
          // Remove nums[i - 1] from nums[i - 1..j] if possible.
          dp[i][j] =
              Math.max(dp[i][j], dp[i - 1][j] + (nums[i - 1] >= queries[dp[i - 1][j]] ? 1 : 0));
        if (j + 1 < n)
          // Remove nums[j + 1] from nums[i..j + 1] if possible.
          dp[i][j] =
              Math.max(dp[i][j], dp[i][j + 1] + (nums[j + 1] >= queries[dp[i][j + 1]] ? 1 : 0));
        if (dp[i][j] == queries.length)
          return queries.length;
      }
    }

    for (int i = 0; i < n; ++i)
      ans = Math.max(ans, dp[i][i] + (nums[i] >= queries[dp[i][i]] ? 1 : 0));

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def maximumProcessableQueries(
      self,
      nums: list[int],
      queries: list[int],
  ) -> int:
    n = len(nums)
    # dp[i][j] := the maximum number of queries processed if nums[i..j] are not
    # removed after processing dp[i][j] queries
    dp = [[0] * n for _ in range(n)]

    for d in range(n - 1, -1, -1):
      for i in range(n):
        j = i + d
        if j >= n:
          continue
        if i > 0:
          # Remove nums[i - 1] from nums[i - 1..j] if possible.
          dp[i][j] = max(dp[i][j], dp[i - 1][j] +
                         (nums[i - 1] >= queries[dp[i - 1][j]]))
        if j + 1 < n:
          # Remove nums[j + 1] from nums[i..j + 1] if possible.
          dp[i][j] = max(dp[i][j], dp[i][j + 1] +
                         (nums[j + 1] >= queries[dp[i][j + 1]]))
        if dp[i][j] == len(queries):
          return len(queries)

    return max(dp[i][i] + (nums[i] >= queries[dp[i][i]])
               for i in range(n))