Problem

Given an array of integers called nums, you can perform any of the following operation while nums contains at least 2 elements:

  • Choose the first two elements of nums and delete them.
  • Choose the last two elements of nums and delete them.
  • Choose the first and the last elements of nums and delete them.

Thescore of the operation is the sum of the deleted elements.

Your task is to find the maximum number of operations that can be performed, such that all operations have the same score.

Return themaximum number of operations possible that satisfy the condition mentioned above.

Examples

Example 1

1
2
3
4
5
6
7

Input: nums = [3,2,1,2,3,4]
Output: 3
Explanation: 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

1
2
3
4
5
6

Input: nums = [3,2,6,1,4]
Output: 2
Explanation: 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

Method 1 – DP with Memoization (Try All Splits)

Intuition

At each step, you can remove the first two, last two, or first and last elements. The score for each operation must be the same. Try all possible first moves, then recursively check if you can continue with the same score. Use memoization to avoid recomputation.

Approach

  1. For all possible ways to remove two elements at the start, end, or both, compute the score and recursively try to maximize the number of operations with that score.
  2. Use memoization to cache results for (left, right, score).
  3. For each possible initial operation, recursively try all valid next operations with the same score.
  4. Return the maximum number of operations found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        function<int(int, int, int)> dfs = [&](int l, int r, int score) {
            if (r - l + 1 < 2) return 0;
            int res = 0;
            if (l + 1 <= r && nums[l] + nums[l+1] == score)
                res = max(res, 1 + dfs(l+2, r, score));
            if (r - 1 >= l && nums[r] + nums[r-1] == score)
                res = max(res, 1 + dfs(l, r-2, score));
            if (l < r && nums[l] + nums[r] == score)
                res = max(res, 1 + dfs(l+1, r-1, score));
            return res;
        };
        if (n < 2) return 0;
        ans = max(ans, 1 + dfs(2, n-1, nums[0] + nums[1]));
        ans = max(ans, 1 + dfs(0, n-3, nums[n-1] + nums[n-2]));
        ans = max(ans, 1 + dfs(1, n-2, nums[0] + nums[n-1]));
        return ans;
    }
};
1

// Omitted for brevity, similar logic as C++ using recursion and memoization.
1

// Omitted for brevity, similar logic as C++ using recursion and memoization.
1

// Omitted for brevity, similar logic as C++ using recursion and memoization.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from functools import cache
class Solution:
    def maxOperations(self, nums: list[int]) -> int:
        n = len(nums)
        @cache
        def dfs(l: int, r: int, score: int) -> int:
            if r - l + 1 < 2:
                return 0
            res = 0
            if l + 1 <= r and nums[l] + nums[l+1] == score:
                res = max(res, 1 + dfs(l+2, r, score))
            if r - 1 >= l and nums[r] + nums[r-1] == score:
                res = max(res, 1 + dfs(l, r-2, score))
            if l < r and nums[l] + nums[r] == score:
                res = max(res, 1 + dfs(l+1, r-1, score))
            return res
        ans = 0
        if n < 2:
            return 0
        ans = max(ans, 1 + dfs(2, n-1, nums[0] + nums[1]))
        ans = max(ans, 1 + dfs(0, n-3, nums[-1] + nums[-2]))
        ans = max(ans, 1 + dfs(1, n-2, nums[0] + nums[-1]))
        return ans
1

// Omitted for brevity, similar logic as C++ using recursion and memoization.

1

// Omitted for brevity, similar logic as C++ using recursion and memoization.

Complexity

  • ⏰ Time complexity: O(n^3), where n is the length of nums, due to all possible splits and memoization.
  • 🧺 Space complexity: O(n^3), for the memoization table.