Maximum Number of Operations With the Same Score II
01 · Problem
You are given an integer array nums. While nums has at least two elements you may perform one of these operations:
- Remove the first two elements.
- Remove the last two elements.
- Remove the first element and the last element.
The score of an operation is the sum of the two removed elements. Every operation you perform must have the same score as all the others. Return the maximum number of operations you can perform. You may stop at any time, and at least one operation is always possible.
02 · Examples
nums = [1,4,2,3,5,0]
3
Remove the first two (1 + 4 = 5) to get [2,3,5,0], remove the first two again (2 + 3 = 5) to get [5,0], then remove them (5 + 0 = 5). That is 3 operations with score 5.
nums = [3,2,6,1,4]
2
Remove the first and last (3 + 4 = 7) to get [2,6,1], then remove the last two (6 + 1 = 7) to get [2]. No more operations are possible.
nums = [5,5,5]
1
Any first operation leaves a single element, so only 1 operation can be performed.
03 · Constraints
- 012 <= nums.length <= 2000
- 020 <= nums[i] <= 1000
- 03Each operation removes exactly two elements: the first two, the last two, or the first and last
- 04Every operation performed must have the same score
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.