LeetCode 3040 - Maximum Number of Operations With the Same Score II

This problem asks us to determine the maximum number of operations that can be performed on an array of integers, where every operation removes two elements from specific positions (either the first two elements, the last two elements, or the first and last elements), and…

leetcodemediumarraydynamic-programmingmemoization

LeetCode Problem 3040

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Memoization

Solution

Problem Understanding

This problem asks us to determine the maximum number of operations that can be performed on an array of integers, where every operation removes two elements from specific positions (either the first two elements, the last two elements, or the first and last elements), and every operation must produce the same score, defined as the sum of the two removed elements. The goal is not to maximize the sum of removed elements, but to maximize the number of operations where each operation’s sum is equal.

The input is a list nums of integers. Its length can be up to 2000, and each element is a positive integer up to 1000. The output is a single integer representing the maximum number of operations where all operation scores are identical.

Key observations include that the array can be manipulated only at the boundaries and the array will shrink as we perform operations. We also need to ensure that for a chosen score, operations can be repeated as many times as possible. Edge cases include arrays with all equal numbers, arrays with strictly increasing or decreasing sequences, and arrays with only two elements.

Approaches

Brute Force Approach

The brute-force approach would involve trying every possible pair of elements that could be removed (first two, last two, first and last), recursively removing them, and keeping track of the score of the first operation. For each recursive path, we would check if all subsequent operations match the initial score. This approach is correct in principle because it explores every valid operation sequence but it is highly inefficient. With an array length of n, there are up to three choices at each step, and the recursion depth could be n/2. This leads to a time complexity of O(3^(n/2)), which is infeasible for n = 2000.

Optimal Approach

A better approach leverages dynamic programming with memoization. The key insight is to consider subarrays [i:j] and record the maximum number of operations for a given sum. Let dp[i][j] represent a dictionary mapping from score to the maximum number of operations for the subarray nums[i:j+1]. At each step, we try removing the first two, last two, or first and last elements and recursively solve for the remaining subarray, updating the dictionary of scores. Finally, we select the maximum count among all possible scores. This approach avoids recalculating results for the same subarray and the same score, reducing redundant computations significantly.

Approach Time Complexity Space Complexity Notes
Brute Force O(3^(n/2)) O(n) Explores all sequences of deletions recursively
Optimal O(n^2 * m) O(n^2 * m) Uses DP with memoization; m is the number of distinct achievable sums

Algorithm Walkthrough

  1. Initialize a memoization table memo that maps (i, j) pairs (subarray boundaries) to dictionaries of {score: max_operations}.
  2. Define a recursive function dfs(i, j) that computes for subarray nums[i:j+1] all possible scores and maximum operation counts.
  3. If i >= j, return an empty dictionary since no more operations are possible.
  4. For the three possible deletions (first two, last two, first and last), calculate the score and recursively call dfs on the remaining subarray.
  5. Merge results: for each returned dictionary, increment the operation count for the current score.
  6. Store the result in memo[(i, j)] to avoid recomputation.
  7. Finally, the result for the whole array dfs(0, n-1) is checked for the maximum number of operations among all scores.

Why it works: The recursive function explores all valid deletion paths while memoization ensures that repeated subarrays are computed only once. By keeping track of the count of operations for each score, we ensure that all operations have the same sum, which satisfies the problem constraints.

Python Solution

from typing import List

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        memo = {}

        def dfs(i: int, j: int):
            if i >= j:
                return {}
            if (i, j) in memo:
                return memo[(i, j)]
            
            res = {}
            # remove first two
            score1 = nums[i] + nums[i+1]
            next1 = dfs(i+2, j)
            res[score1] = 1 + next1.get(score1, 0)

            # remove last two
            score2 = nums[j-1] + nums[j]
            next2 = dfs(i, j-2)
            res[score2] = max(res.get(score2, 0), 1 + next2.get(score2, 0))

            # remove first and last
            score3 = nums[i] + nums[j]
            next3 = dfs(i+1, j-1)
            res[score3] = max(res.get(score3, 0), 1 + next3.get(score3, 0))

            memo[(i, j)] = res
            return res

        final_res = dfs(0, n-1)
        return max(final_res.values(), default=0)

The implementation defines a dfs function that recursively computes the maximum number of operations for each score. We check all three deletion strategies and merge results, using max to ensure the optimal count for each score is stored. Memoization avoids recalculating results for the same subarray.

Go Solution

func maxOperations(nums []int) int {
    n := len(nums)
    memo := make(map[[2]int]map[int]int)

    var dfs func(i, j int) map[int]int
    dfs = func(i, j int) map[int]int {
        if i >= j {
            return map[int]int{}
        }
        key := [2]int{i, j}
        if val, ok := memo[key]; ok {
            return val
        }

        res := make(map[int]int)

        // remove first two
        score1 := nums[i] + nums[i+1]
        next1 := dfs(i+2, j)
        res[score1] = 1 + next1[score1]

        // remove last two
        score2 := nums[j-1] + nums[j]
        next2 := dfs(i, j-2)
        if count, ok := next2[score2]; ok && 1+count > res[score2] {
            res[score2] = 1 + count
        }

        // remove first and last
        score3 := nums[i] + nums[j]
        next3 := dfs(i+1, j-1)
        if count, ok := next3[score3]; ok && 1+count > res[score3] {
            res[score3] = 1 + count
        } else if _, exists := res[score3]; !exists {
            res[score3] = 1
        }

        memo[key] = res
        return res
    }

    finalRes := dfs(0, n-1)
    maxOps := 0
    for _, v := range finalRes {
        if v > maxOps {
            maxOps = v
        }
    }
    return maxOps
}

The Go version mirrors the Python implementation, with maps used for memoization and result dictionaries. Care is taken to initialize maps properly and handle cases where a key does not exist.

Worked Examples

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

Step Action Remaining Array Score Total Ops
1 remove first two [1,2,3,4] 5 1
2 remove first and last [2,3] 5 2
3 remove first and last [] 5 3

Result: 3 operations with score 5.

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

Step Action Remaining Array Score Total Ops
1 remove first two [6,1,4] 5 1
2 remove last two [6] 5 2

Result: 2 operations with score 5.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 * m) For each subarray [i:j], we track at most m distinct scores. Each subarray is computed once due to memoization.
Space O(n^2 * m) Memoization stores results for all subarrays [i:j] and associated score counts.

The algorithm is feasible for n <= 2000 and values up to 1000.

Test Cases

# Provided examples
assert Solution().maxOperations([3,2,1,2,3,4]) == 3
assert Solution().maxOperations([3,2,6,1,4]) == 2

# Edge cases
assert Solution().maxOperations([1,1]) == 1  # minimum array
assert Solution().maxOperations([1,2,3,4,5,6,7,8,9,10]) == 5  # consecutive numbers
assert Solution().maxOperations([5,5