Watch 10 video solutions for Maximum Number of Operations With the Same Score II, a medium level problem involving Array, Dynamic Programming, Memoization. This walkthrough by NeetCodeIO has 8,968 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 1000