Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
Given an array of integers called nums, you can perform any of the following operation while nums contains at least 2 elements:
nums and delete them.nums and delete them.nums and delete them.The score 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 the maximum number of operations possible that satisfy the condition mentioned above.
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] <= 1000Problem summary: 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. The score 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 the maximum number of operations possible that satisfy the condition mentioned above.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Dynamic Programming
[3,2,1,2,3,4]
[3,2,6,1,4]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3040: Maximum Number of Operations With the Same Score II
class Solution {
private Integer[][] f;
private int[] nums;
private int s;
private int n;
public int maxOperations(int[] nums) {
this.nums = nums;
n = nums.length;
int a = g(2, n - 1, nums[0] + nums[1]);
int b = g(0, n - 3, nums[n - 2] + nums[n - 1]);
int c = g(1, n - 2, nums[0] + nums[n - 1]);
return 1 + Math.max(a, Math.max(b, c));
}
private int g(int i, int j, int s) {
f = new Integer[n][n];
this.s = s;
return dfs(i, j);
}
private int dfs(int i, int j) {
if (j - i < 1) {
return 0;
}
if (f[i][j] != null) {
return f[i][j];
}
int ans = 0;
if (nums[i] + nums[i + 1] == s) {
ans = Math.max(ans, 1 + dfs(i + 2, j));
}
if (nums[i] + nums[j] == s) {
ans = Math.max(ans, 1 + dfs(i + 1, j - 1));
}
if (nums[j - 1] + nums[j] == s) {
ans = Math.max(ans, 1 + dfs(i, j - 2));
}
return f[i][j] = ans;
}
}
// Accepted solution for LeetCode #3040: Maximum Number of Operations With the Same Score II
func maxOperations(nums []int) int {
n := len(nums)
var g func(i, j, s int) int
g = func(i, j, s int) int {
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if j-i < 1 {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := 0
if nums[i]+nums[i+1] == s {
ans = max(ans, 1+dfs(i+2, j))
}
if nums[i]+nums[j] == s {
ans = max(ans, 1+dfs(i+1, j-1))
}
if nums[j-1]+nums[j] == s {
ans = max(ans, 1+dfs(i, j-2))
}
f[i][j] = ans
return ans
}
return dfs(i, j)
}
a := g(2, n-1, nums[0]+nums[1])
b := g(0, n-3, nums[n-1]+nums[n-2])
c := g(1, n-2, nums[0]+nums[n-1])
return 1 + max(a, b, c)
}
# Accepted solution for LeetCode #3040: Maximum Number of Operations With the Same Score II
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)
// Accepted solution for LeetCode #3040: Maximum Number of Operations With the Same Score II
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3040: Maximum Number of Operations With the Same Score II
// class Solution {
// private Integer[][] f;
// private int[] nums;
// private int s;
// private int n;
//
// public int maxOperations(int[] nums) {
// this.nums = nums;
// n = nums.length;
// int a = g(2, n - 1, nums[0] + nums[1]);
// int b = g(0, n - 3, nums[n - 2] + nums[n - 1]);
// int c = g(1, n - 2, nums[0] + nums[n - 1]);
// return 1 + Math.max(a, Math.max(b, c));
// }
//
// private int g(int i, int j, int s) {
// f = new Integer[n][n];
// this.s = s;
// return dfs(i, j);
// }
//
// private int dfs(int i, int j) {
// if (j - i < 1) {
// return 0;
// }
// if (f[i][j] != null) {
// return f[i][j];
// }
// int ans = 0;
// if (nums[i] + nums[i + 1] == s) {
// ans = Math.max(ans, 1 + dfs(i + 2, j));
// }
// if (nums[i] + nums[j] == s) {
// ans = Math.max(ans, 1 + dfs(i + 1, j - 1));
// }
// if (nums[j - 1] + nums[j] == s) {
// ans = Math.max(ans, 1 + dfs(i, j - 2));
// }
// return f[i][j] = ans;
// }
// }
// Accepted solution for LeetCode #3040: Maximum Number of Operations With the Same Score II
function maxOperations(nums: number[]): number {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(n));
const g = (i: number, j: number, s: number): number => {
f.forEach(row => row.fill(-1));
const dfs = (i: number, j: number): number => {
if (j - i < 1) {
return 0;
}
if (f[i][j] !== -1) {
return f[i][j];
}
let ans = 0;
if (nums[i] + nums[i + 1] === s) {
ans = Math.max(ans, 1 + dfs(i + 2, j));
}
if (nums[i] + nums[j] === s) {
ans = Math.max(ans, 1 + dfs(i + 1, j - 1));
}
if (nums[j - 1] + nums[j] === s) {
ans = Math.max(ans, 1 + dfs(i, j - 2));
}
return (f[i][j] = ans);
};
return dfs(i, j);
};
const a = g(2, n - 1, nums[0] + nums[1]);
const b = g(0, n - 3, nums[n - 2] + nums[n - 1]);
const c = g(1, n - 2, nums[0] + nums[n - 1]);
return 1 + Math.max(a, b, c);
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.