You are given an array of integers nums. You must repeatedly perform one of the following operations while the array has more than two elements:
For each operation, add the sum of the removed elements to your total score.
Return the maximum possible score you can achieve.
Example 1:
Input: nums = [2,4,1]
Output: 6
Explanation:
The possible operations are:
(2 + 4) = 6. The remaining array is [1].(4 + 1) = 5. The remaining array is [2].(2 + 1) = 3. The remaining array is [4].The maximum score is obtained by removing the first two elements, resulting in a final score of 6.
Example 2:
Input: nums = [5,-1,4,2]
Output: 7
Explanation:
The possible operations are:
(5 + 2) = 7. The remaining array is [-1, 4].(5 + -1) = 4. The remaining array is [4, 2].(4 + 2) = 6. The remaining array is [5, -1].The maximum score is obtained by removing the first and last elements, resulting in a total score of 7.
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104According to the problem description, each operation removes the two elements at the endpoints. Therefore, when the number of elements is odd, one element will eventually remain; when the number of elements is even, two consecutive elements in the array will eventually remain.
To maximize the score after deletions, we should minimize the remaining elements.
Thus, if the array nums has an odd number of elements, the answer is the sum of all elements s in the array nums minus the minimum value mi in nums; if the array nums has an even number of elements, the answer is the sum of all elements s in the array nums minus the minimum sum of any two consecutive elements.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Java
C++
Go
TypeScript
Practice Maximize Score After Pair Deletions with our built-in code editor and test cases.
Practice on FleetCode