Skip to content

3040. Maximum Number of Operations With the Same Score II 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
34
35
36
37
38
39
class Solution {
 public:
  int maxOperations(vector<int>& nums) {
    const int n = nums.size();
    unordered_map<string, int> mem;
    return max({maxOperations(nums, 0, n - 1, nums[0] + nums[1], mem),
                maxOperations(nums, 0, n - 1, nums[n - 1] + nums[n - 2], mem),
                maxOperations(nums, 0, n - 1, nums[0] + nums[n - 1], mem)});
  }

 private:
  // Returns the maximum number of operations that can be performed for
  // nums[i..j], s.t. all operations have the same `score`.
  int maxOperations(const vector<int>& nums, int i, int j, int score,
                    unordered_map<string, int>& mem) {
    if (i >= j)
      return 0;
    const string key = hash(i, j, score);
    if (const auto it = mem.find(key); it != mem.end())
      return it->second;
    const int deleteFirstTwo =
        nums[i] + nums[i + 1] == score
            ? 1 + maxOperations(nums, i + 2, j, score, mem)
            : 0;
    const int deleteLastTwo =
        nums[j] + nums[j - 1] == score
            ? 1 + maxOperations(nums, i, j - 2, score, mem)
            : 0;
    const int deleteFirstAndLast =
        nums[i] + nums[j] == score
            ? 1 + maxOperations(nums, i + 1, j - 1, score, mem)
            : 0;
    return mem[key] = max({deleteFirstTwo, deleteLastTwo, deleteFirstAndLast});
  }

  string hash(int i, int j, int score) {
    return to_string(i) + "," + to_string(j) + "," + to_string(score);
  }
};

 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
class Solution {
  public int maxOperations(int[] nums) {
    final int n = nums.length;
    Map<String, Integer> mem = new HashMap<>();
    return Math.max(Math.max(maxOperations(nums, 0, n - 1, nums[0] + nums[1], mem),
                             maxOperations(nums, 0, n - 1, nums[n - 1] + nums[n - 2], mem)),
                    maxOperations(nums, 0, n - 1, nums[0] + nums[n - 1], mem));
  }

  // Returns the maximum number of operations that can be performed for
  // nums[i..j], s.t. all operations have the same `score`.
  private int maxOperations(int[] nums, int i, int j, int score, Map<String, Integer> mem) {
    if (i >= j)
      return 0;
    final String key = hash(i, j, score);
    if (mem.containsKey(key))
      return mem.get(key);
    final int deleteFirstTwo =
        nums[i] + nums[i + 1] == score ? 1 + maxOperations(nums, i + 2, j, score, mem) : 0;
    final int deleteLastTwo =
        nums[j] + nums[j - 1] == score ? 1 + maxOperations(nums, i, j - 2, score, mem) : 0;
    final int deleteFirstAndLast =
        nums[i] + nums[j] == score ? 1 + maxOperations(nums, i + 1, j - 1, score, mem) : 0;
    mem.put(key, Math.max(Math.max(deleteFirstTwo, deleteLastTwo), deleteFirstAndLast));
    return mem.get(key);
  }

  private String hash(int i, int j, int score) {
    return i + "," + j + "," + score;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def maxOperations(self, nums: list[int]) -> int:
    @functools.lru_cache(None)
    def dp(i: int, j: int, score: int) -> int:
      """
      Returns the maximum number of operations that can be performed for
      nums[i..j], s.t. all operations have the same `score`.
      """
      if i >= j:
        return 0
      deleteFirstTwo = (1 + dp(i + 2, j, score)
                        if nums[i] + nums[i + 1] == score else 0)
      deleteLastTwo = (1 + dp(i, j - 2, score)
                       if nums[j] + nums[j - 1] == score else 0)
      deleteFirstAndLast = (1 + dp(i + 1, j - 1, score)
                            if nums[i] + nums[j] == score else 0)
      return max(deleteFirstTwo, deleteLastTwo, deleteFirstAndLast)

    n = len(nums)
    return max(dp(0, n - 1, nums[0] + nums[1]),
               dp(0, n - 1, nums[-1] + nums[-2]),
               dp(0, n - 1, nums[0] + nums[-1]))