Maximum Number of Operations With the Same Score II
Given an array of integers called nums, you can perform any of the following operations 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.
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
3The operations delete pairs with sums 5: first two, then first and last, then first and last again, for 3 total operations.
Example 2
Input
nums = [3,2,6,1,4]Output
2Deleting the first two elements and then the last two elements both have score 5, and it can be proven that at most 2 operations are possible.
Constraints
- 2 <= nums.length <= 2000
- 1 <= nums[i] <= 1000