Maximum Number of Operations With the Same Score II
MediumUpdated: Aug 2, 2025
Practice on:
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
numsand delete them. - Choose the last two elements of
numsand delete them. - Choose the first and the last elements of
numsand 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
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
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 <= 20001 <= 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
- 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.
- Use memoization to cache results for (left, right, score).
- For each possible initial operation, recursively try all valid next operations with the same score.
- Return the maximum number of operations found.
Code
C++
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;
}
};
Go
func maxOperations(nums []int) int {
n := len(nums)
if n < 2 {
return 0
}
// Memoization map
memo := make(map[string]int)
var dfs func(l, r, score int) int
dfs = func(l, r, score int) int {
if r-l+1 < 2 {
return 0
}
key := fmt.Sprintf("%d,%d,%d", l, r, score)
if val, exists := memo[key]; exists {
return val
}
res := 0
// Try removing first two elements
if l+1 <= r && nums[l]+nums[l+1] == score {
res = max(res, 1+dfs(l+2, r, score))
}
// Try removing last two elements
if r-1 >= l && nums[r]+nums[r-1] == score {
res = max(res, 1+dfs(l, r-2, score))
}
// Try removing first and last elements
if l < r && nums[l]+nums[r] == score {
res = max(res, 1+dfs(l+1, r-1, score))
}
memo[key] = res
return res
}
ans := 0
// Try all three possible first operations
ans = max(ans, 1+dfs(2, n-1, nums[0]+nums[1])) // Remove first two
ans = max(ans, 1+dfs(0, n-3, nums[n-1]+nums[n-2])) // Remove last two
ans = max(ans, 1+dfs(1, n-2, nums[0]+nums[n-1])) // Remove first and last
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Java
class Solution {
private Map<String, Integer> memo = new HashMap<>();
private int[] nums;
public int maxOperations(int[] nums) {
this.nums = nums;
int n = nums.length;
if (n < 2) return 0;
int ans = 0;
// Try all three possible first operations
ans = Math.max(ans, 1 + dfs(2, n - 1, nums[0] + nums[1])); // Remove first two
ans = Math.max(ans, 1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2])); // Remove last two
ans = Math.max(ans, 1 + dfs(1, n - 2, nums[0] + nums[n - 1])); // Remove first and last
return ans;
}
private int dfs(int l, int r, int score) {
if (r - l + 1 < 2) {
return 0;
}
String key = l + "," + r + "," + score;
if (memo.containsKey(key)) {
return memo.get(key);
}
int res = 0;
// Try removing first two elements
if (l + 1 <= r && nums[l] + nums[l + 1] == score) {
res = Math.max(res, 1 + dfs(l + 2, r, score));
}
// Try removing last two elements
if (r - 1 >= l && nums[r] + nums[r - 1] == score) {
res = Math.max(res, 1 + dfs(l, r - 2, score));
}
// Try removing first and last elements
if (l < r && nums[l] + nums[r] == score) {
res = Math.max(res, 1 + dfs(l + 1, r - 1, score));
}
memo.put(key, res);
return res;
}
}
Kotlin
import kotlin.math.max
class Solution {
private val memo = mutableMapOf<String, Int>()
private lateinit var nums: IntArray
fun maxOperations(nums: IntArray): Int {
this.nums = nums
val n = nums.size
if (n < 2) return 0
var ans = 0
// Try all three possible first operations
ans = max(ans, 1 + dfs(2, n - 1, nums[0] + nums[1])) // Remove first two
ans = max(ans, 1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2])) // Remove last two
ans = max(ans, 1 + dfs(1, n - 2, nums[0] + nums[n - 1])) // Remove first and last
return ans
}
private fun dfs(l: Int, r: Int, score: Int): Int {
if (r - l + 1 < 2) {
return 0
}
val key = "$l,$r,$score"
if (key in memo) {
return memo[key]!!
}
var res = 0
// Try removing first two elements
if (l + 1 <= r && nums[l] + nums[l + 1] == score) {
res = max(res, 1 + dfs(l + 2, r, score))
}
// Try removing last two elements
if (r - 1 >= l && nums[r] + nums[r - 1] == score) {
res = max(res, 1 + dfs(l, r - 2, score))
}
// Try removing first and last elements
if (l < r && nums[l] + nums[r] == score) {
res = max(res, 1 + dfs(l + 1, r - 1, score))
}
memo[key] = res
return res
}
}
Python
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]))
##### Rust
```rust
use std::collections::HashMap;
impl Solution {
pub fn max_operations(nums: Vec<i32>) -> i32 {
let n = nums.len();
if n < 2 {
return 0;
}
let mut memo = HashMap::new();
fn dfs(
l: usize,
r: usize,
score: i32,
nums: &Vec<i32>,
memo: &mut HashMap<String, i32>,
) -> i32 {
if r < l || r - l + 1 < 2 {
return 0;
}
let key = format!("{},{},{}", l, r, score);
if let Some(&val) = memo.get(&key) {
return val;
}
let mut res = 0;
// Try removing first two elements
if l + 1 <= r && nums[l] + nums[l + 1] == score {
res = res.max(1 + dfs(l + 2, r, score, nums, memo));
}
// Try removing last two elements
if r >= 1 && r - 1 >= l && nums[r] + nums[r - 1] == score {
res = res.max(1 + dfs(l, r - 2, score, nums, memo));
}
// Try removing first and last elements
if l < r && nums[l] + nums[r] == score {
res = res.max(1 + dfs(l + 1, r - 1, score, nums, memo));
}
memo.insert(key, res);
res
}
let mut ans = 0;
// Try all three possible first operations
ans = ans.max(1 + dfs(2, n - 1, nums[0] + nums[1], &nums, &mut memo)); // Remove first two
ans = ans.max(1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2], &nums, &mut memo)); // Remove last two
ans = ans.max(1 + dfs(1, n - 2, nums[0] + nums[n - 1], &nums, &mut memo)); // Remove first and last
ans
}
}
TypeScript
function maxOperations(nums: number[]): number {
const n = nums.length;
if (n < 2) return 0;
const memo = new Map<string, number>();
const dfs = (l: number, r: number, score: number): number => {
if (r - l + 1 < 2) {
return 0;
}
const key = `${l},${r},${score}`;
if (memo.has(key)) {
return memo.get(key)!;
}
let res = 0;
// Try removing first two elements
if (l + 1 <= r && nums[l] + nums[l + 1] === score) {
res = Math.max(res, 1 + dfs(l + 2, r, score));
}
// Try removing last two elements
if (r - 1 >= l && nums[r] + nums[r - 1] === score) {
res = Math.max(res, 1 + dfs(l, r - 2, score));
}
// Try removing first and last elements
if (l < r && nums[l] + nums[r] === score) {
res = Math.max(res, 1 + dfs(l + 1, r - 1, score));
}
memo.set(key, res);
return res;
};
let ans = 0;
// Try all three possible first operations
ans = Math.max(ans, 1 + dfs(2, n - 1, nums[0] + nums[1])); // Remove first two
ans = Math.max(ans, 1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2])); // Remove last two
ans = Math.max(ans, 1 + dfs(1, n - 2, nums[0] + nums[n - 1])); // Remove first and last
return ans;
}
Complexity
- ⏰ Time complexity:
O(n^3), wherenis the length ofnums, due to all possible splits and memoization. - 🧺 Space complexity:
O(n^3), for the memoization table.