You are given an array of integers nums. Consider the following operation:
nums and define the score of the operation as the sum of these two elements.You can perform this operation until nums contains fewer than two elements. Additionally, the same score must be achieved in all operations.
Return the maximum number of operations you can perform.
Example 1:
Input: nums = [3,2,1,4,5]
Output: 2
Explanation:
3 + 2 = 5. After this operation, nums = [1,4,5].4 + 1 = 5, the same as the previous operation. After this operation, nums = [5].Example 2:
Input: nums = [1,5,3,3,4,1,3,2,2,3]
Output: 2
Explanation:
1 + 5 = 6. After this operation, nums = [3,3,4,1,3,2,2,3].3 + 3 = 6, the same as the previous operation. After this operation, nums = [4,1,3,2,2,3].4 + 1 = 5, which is different from the previous scores.Example 3:
Input: nums = [5,3]
Output: 1
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 1000This solution iterates over the array, using each possible score from the first pair of numbers as a potential target score. It then attempts to match that score with subsequent pairs, counting the number of successful operations. We return the maximum number of operations achieved with any target score.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), Space Complexity: O(1), where n is the number of elements in nums.
This code iterates with a target starting from the first two elements, checks forward if more such operations exist, and counts them. This eliminates redundant backward checks.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), but optimized and often faster in practice, Space Complexity: O(1), since only constant space is used.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), Space Complexity: O(1), where n is the number of elements in |
| Optimized Two-Pointer Approach | Time Complexity: O(n^2), but optimized and often faster in practice, Space Complexity: O(1), since only constant space is used. |
3040. Maximum Number of Operations With the Same Score II | Standard DP✅ • Aryan Mittal • 1,883 views views
Watch 9 more video solutions →Practice Maximum Number of Operations With the Same Score I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor