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] <= 1000In #3040 Maximum Number of Operations With the Same Score II, the key idea is that the first operation determines the target score. Each operation removes exactly two numbers, and every subsequent operation must produce the same sum. Since removals can only occur from the boundaries of the array, the valid choices at any step are limited.
A common strategy is to try all possible initial operations (such as removing the first two elements, the last two elements, or the first and last element). Once the target score is fixed, we recursively evaluate the remaining subarray. For every state defined by indices l and r, we check if any valid pair from the boundaries matches the required score.
To avoid recomputation, use memoization (top-down dynamic programming) to store results for each subarray range. This significantly reduces redundant exploration and keeps the algorithm efficient.
The resulting solution explores valid boundary removals while caching intermediate results, leading to roughly quadratic complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Memoization | O(n^2) | O(n^2) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
After the first operation, the score of other operations is fixed.
For the fixed score use dynamic programming <code>dp[l][r]</code> to find a maximum number of operations on the subarray <code>nums[l..r]</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Memoization prevents recalculating results for the same subarray range multiple times. Since many recursive paths reach the same (l, r) boundaries, caching results significantly reduces the total number of computations.
Yes, problems like this appear in coding interviews because they test dynamic programming, recursion, and state reduction techniques. Variants of boundary-removal or interval DP problems are common in technical interviews.
A 2D DP cache or memoization table is typically used to store results for subarray states defined by left and right indices. This structure allows efficient lookup of previously computed results.
The optimal approach uses dynamic programming with memoization. After fixing the score from the first operation, recursively explore valid boundary pairs that match this score while caching results for each subarray to avoid recomputation.