Question

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

中文文档

Description

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._

 

Example 1:

Input: nums = [1,2,3,4,5], queries = [1,2,3,4,6]
Output: 4
Explanation: We don't do any operation and process the queries as follows:
1- We choose and remove nums[0] since 1 <= 1, then nums becomes [2,3,4,5].
2- We choose and remove nums[0] since 2 <= 2, then nums becomes [3,4,5].
3- We choose and remove nums[0] since 3 <= 3, then nums becomes [4,5].
4- We choose and remove nums[0] since 4 <= 4, then nums becomes [5].
5- We can not choose any elements from nums since they are not greater than or equal to 5.
Hence, the answer is 4.
It can be shown that we can't process more than 4 queries.

Example 2:

Input: nums = [2,3,2], queries = [2,2,3]
Output: 3
Explanation: We don't do any operation and process the queries as follows:
1- We choose and remove nums[0] since 2 <= 2, then nums becomes [3,2].
2- We choose and remove nums[1] since 2 <= 2, then nums becomes [3].
3- We choose and remove nums[0] since 3 <= 3, then nums becomes [].
Hence, the answer is 3.
It can be shown that we can't process more than 3 queries.

Example 3:

Input: nums = [3,4,3], queries = [4,3,2]
Output: 2
Explanation: First we replace nums with the subsequence of nums [4,3].
Then we can process the queries as follows:
1- We choose and remove nums[0] since 4 <= 4, then nums becomes [3].
2- We choose and remove nums[0] since 3 <= 3, then nums becomes [].
3- We can not process any more queries since nums is empty.
Hence, the answer is 2.
It can be shown that we can't process more than 2 queries.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= queries.length <= 1000
• 1 <= nums[i], queries[i] <= 109

Solutions

Solution 1: Dynamic Programming

We define $f[i][j]$ as the maximum number of queries we can handle when the numbers in the interval $[i, j]$ have not been deleted yet.

Consider $f[i][j]$:

• If $i > 0$, the value of $f[i][j]$ can be transferred from $f[i - 1][j]$. If $nums[i - 1] \ge queries[f[i - 1][j]]$, we can choose to delete $nums[i - 1]$. Therefore, we have $f[i][j] = f[i - 1][j] + (nums[i - 1] \ge queries[f[i - 1][j]])$.
• If $j + 1 < n$, the value of $f[i][j]$ can be transferred from $f[i][j + 1]$. If $nums[j + 1] \ge queries[f[i][j + 1]]$, we can choose to delete $nums[j + 1]$. Therefore, we have $f[i][j] = f[i][j + 1] + (nums[j + 1] \ge queries[f[i][j + 1]])$.
• If $f[i][j] = m$, we can directly return $m$.

The final answer is $\max\limits_{0 \le i < n} f[i][i] + (nums[i] \ge queries[f[i][i]])$.

The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the array $nums$.

class Solution:
  def maximumProcessableQueries(self, nums: List[int], queries: List[int]) -> int:
    n = len(nums)
    f = [[0] * n for _ in range(n)]
    m = len(queries)
    for i in range(n):
      for j in range(n - 1, i - 1, -1):
        if i:
          f[i][j] = max(
            f[i][j], f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]])
          )
        if j + 1 < n:
          f[i][j] = max(
            f[i][j], f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]])
          )
        if f[i][j] == m:
          return m
    return max(f[i][i] + (nums[i] >= queries[f[i][i]]) for i in range(n))

class Solution {
  public int maximumProcessableQueries(int[] nums, int[] queries) {
    int n = nums.length;
    int[][] f = new int[n][n];
    int m = queries.length;
    for (int i = 0; i < n; ++i) {
      for (int j = n - 1; j >= i; --j) {
        if (i > 0) {
          f[i][j] = Math.max(
            f[i][j], f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]] ? 1 : 0));
        }
        if (j + 1 < n) {
          f[i][j] = Math.max(
            f[i][j], f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]] ? 1 : 0));
        }
        if (f[i][j] == m) {
          return m;
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = Math.max(ans, f[i][i] + (nums[i] >= queries[f[i][i]] ? 1 : 0));
    }
    return ans;
  }
}

class Solution {
public:
  int maximumProcessableQueries(vector<int>& nums, vector<int>& queries) {
    int n = nums.size();
    int f[n][n];
    memset(f, 0, sizeof(f));
    int m = queries.size();
    for (int i = 0; i < n; ++i) {
      for (int j = n - 1; j >= i; --j) {
        if (i > 0) {
          f[i][j] = max(f[i][j], f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]] ? 1 : 0));
        }
        if (j + 1 < n) {
          f[i][j] = max(f[i][j], f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]] ? 1 : 0));
        }
        if (f[i][j] == m) {
          return m;
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = max(ans, f[i][i] + (nums[i] >= queries[f[i][i]] ? 1 : 0));
    }
    return ans;
  }
};

func maximumProcessableQueries(nums []int, queries []int) (ans int) {
  n := len(nums)
  f := make([][]int, n)
  for i := range f {
    f[i] = make([]int, n)
  }
  m := len(queries)
  for i := 0; i < n; i++ {
    for j := n - 1; j >= i; j-- {
      if i > 0 {
        t := 0
        if nums[i-1] >= queries[f[i-1][j]] {
          t = 1
        }
        f[i][j] = max(f[i][j], f[i-1][j]+t)
      }
      if j+1 < n {
        t := 0
        if nums[j+1] >= queries[f[i][j+1]] {
          t = 1
        }
        f[i][j] = max(f[i][j], f[i][j+1]+t)
      }
      if f[i][j] == m {
        return m
      }
    }
  }
  for i := 0; i < n; i++ {
    t := 0
    if nums[i] >= queries[f[i][i]] {
      t = 1
    }
    ans = max(ans, f[i][i]+t)
  }
  return
}

function maximumProcessableQueries(nums: number[], queries: number[]): number {
  const n = nums.length;
  const f: number[][] = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));
  const m = queries.length;
  for (let i = 0; i < n; ++i) {
    for (let j = n - 1; j >= i; --j) {
      if (i > 0) {
        f[i][j] = Math.max(
          f[i][j],
          f[i - 1][j] + (nums[i - 1] >= queries[f[i - 1][j]] ? 1 : 0),
        );
      }
      if (j + 1 < n) {
        f[i][j] = Math.max(
          f[i][j],
          f[i][j + 1] + (nums[j + 1] >= queries[f[i][j + 1]] ? 1 : 0),
        );
      }
      if (f[i][j] == m) {
        return m;
      }
    }
  }
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    ans = Math.max(ans, f[i][i] + (nums[i] >= queries[f[i][i]] ? 1 : 0));
  }
  return ans;
}