#3040

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Number of Operations With the Same Score II

This problem asks to maximize operations on an integer array where all deletions produce the same score using dynamic programming.

array dynamic programming memoization

Problem Statement

Given an integer array nums, you can repeatedly remove any two elements while at least two elements remain. Each removal yields a score equal to the sum of the two elements removed.

Determine the maximum number of operations that can be performed such that every operation results in the same score. The order of removal and pair selection affects the total number of valid operations, and dynamic programming is key to exploring all possibilities.

Examples

Example 1

Input: nums = [3,2,1,2,3,4]

Output: 3

We perform the following operations:

Delete the first two elements, with score 3 + 2 = 5, nums = [1,2,3,4].
Delete the first and the last elements, with score 1 + 4 = 5, nums = [2,3].
Delete the first and the last elements, with score 2 + 3 = 5, nums = []. We are unable to perform any more operations as nums is empty.

Example 2

Input: nums = [3,2,6,1,4]

Output: 2

We perform the following operations:

Delete the first two elements, with score 3 + 2 = 5, nums = [6,1,4].
Delete the last two elements, with score 1 + 4 = 5, nums = [6]. It can be proven that we can perform at most 2 operations.

Constraints

2 <= nums.length <= 2000
1 <= nums[i] <= 1000

Solution Approach

Identify all possible scores

First, calculate every possible sum of pairs in nums to establish candidate operation scores. These scores form the basis for state transitions in the dynamic programming solution.

Dynamic programming with memoization

Define a DP state representing the current array configuration and target score. Use memoization to store results for subarrays and partial operations, avoiding repeated calculations of the same state.

Iterative pair selection and recursion

Recursively remove valid pairs matching the target score, updating the array and DP state. Track the number of successful operations and return the maximum count after exploring all removal sequences.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depends on the DP implementation. A naive recursive approach may reach O(2^n), but memoization reduces repeated state computations. With optimized DP, expect time O(n^3) in worst case and space O(n^2) for storing subarray results.

What Interviewers Usually Probe

Focus on state transition dynamic programming with memoization to avoid redundant calculations.
Consider how pair selection order affects maximum operations with the same score.
Highlight that after choosing the first operation, the score of subsequent operations is fixed and drives DP decisions.

Common Pitfalls or Variants

Common pitfalls

Forgetting to fix the score after the first operation, leading to inconsistent totals.
Not using memoization, which causes timeouts on larger arrays.
Assuming any pair sum works without verifying it maintains the same score across all operations.

Follow-up variants

Allow operations that remove more than two elements while keeping the score consistent.
Count the maximum operations but with a limited number of total deletions.
Extend to arrays with negative integers and track valid operation sequences.

FAQ

What pattern is used in Maximum Number of Operations With the Same Score II?

State transition dynamic programming is applied to explore all valid pair removals while maintaining the same score.

Can I use a greedy approach for this problem?

A greedy approach often fails because removing the largest pair first may prevent maximizing total operations; DP ensures correctness.

What is the role of memoization here?

Memoization stores results for each subarray and score combination, reducing recomputation and preventing exponential time complexity.

How do I handle arrays where multiple pairs have the same sum?

Consider all pairs as candidates in DP; recursion with memoization ensures all combinations are explored for maximum operations.

What are the constraints to consider in this problem?

Arrays have length 2 to 2000, with element values between 1 and 1000. Efficient DP is needed to handle larger inputs within time limits.

terminal

Solution

Solution 1: Memorization Search

There are three possible values for the score $s$, which are $s = nums[0] + nums[1]$, $s = nums[0] + nums[n-1]$, and $s = nums[n-1] + nums[n-2]$. We can perform memorization search for these three cases separately.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, s: int) -> int:
            if j - i < 1:
                return 0
            ans = 0
            if nums[i] + nums[i + 1] == s:
                ans = max(ans, 1 + dfs(i + 2, j, s))
            if nums[i] + nums[j] == s:
                ans = max(ans, 1 + dfs(i + 1, j - 1, s))
            if nums[j - 1] + nums[j] == s:
                ans = max(ans, 1 + dfs(i, j - 2, s))
            return ans

        n = len(nums)
        a = dfs(2, n - 1, nums[0] + nums[1])
        b = dfs(0, n - 3, nums[-1] + nums[-2])
        c = dfs(1, n - 2, nums[0] + nums[-1])
        return 1 + max(a, b, c)

Continue Practicing

#2920 maximum points after collecting coins from all nodes #2713 maximum strictly increasing cells in a matrix #3459 length of longest v shaped diagonal segment