3040. Maximum Number of Operations With the Same Score II LeetCode Solution
In this guide, you will get 3040. Maximum Number of Operations With the Same Score II LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Operations With the Same Score II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Operations With the Same Score II
Given an array of integers called nums, you can perform any of the following operation while nums contains at least 2 elements:
Choose the first two elements of nums and delete them.
Choose the last two elements of nums and delete them.
Choose the first and the last elements of 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.
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 <= 2000
1 <= nums[i] <= 1000
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3040. Maximum Number of Operations With the Same Score II LeetCode Solution in C++
class Solution {
public:
int maxOperations(vector<int>& nums) {
const int n = nums.size();
unordered_map<string, int> mem;
return max({maxOperations(nums, 0, n - 1, nums[0] + nums[1], mem),
maxOperations(nums, 0, n - 1, nums[n - 1] + nums[n - 2], mem),
maxOperations(nums, 0, n - 1, nums[0] + nums[n - 1], mem)});
}
private:
// Returns the maximum number of operations that can be performed for
// nums[i..j], s.t. all operations have the same `score`.
int maxOperations(const vector<int>& nums, int i, int j, int score,
unordered_map<string, int>& mem) {
if (i >= j)
return 0;
const string key = hash(i, j, score);
if (const auto it = mem.find(key); it != mem.end())
return it->second;
const int deleteFirstTwo =
nums[i] + nums[i + 1] == score
? 1 + maxOperations(nums, i + 2, j, score, mem)
: 0;
const int deleteLastTwo =
nums[j] + nums[j - 1] == score
? 1 + maxOperations(nums, i, j - 2, score, mem)
: 0;
const int deleteFirstAndLast =
nums[i] + nums[j] == score
? 1 + maxOperations(nums, i + 1, j - 1, score, mem)
: 0;
return mem[key] = max({deleteFirstTwo, deleteLastTwo, deleteFirstAndLast});
}
string hash(int i, int j, int score) {
return to_string(i) + "," + to_string(j) + "," + to_string(score);
}
}; /* code provided by PROGIEZ */
3040. Maximum Number of Operations With the Same Score II LeetCode Solution in Java
class Solution {
public int maxOperations(int[] nums) {
final int n = nums.length;
Map<String, Integer> mem = new HashMap<>();
return Math.max(Math.max(maxOperations(nums, 0, n - 1, nums[0] + nums[1], mem),
maxOperations(nums, 0, n - 1, nums[n - 1] + nums[n - 2], mem)),
maxOperations(nums, 0, n - 1, nums[0] + nums[n - 1], mem));
}
// Returns the maximum number of operations that can be performed for
// nums[i..j], s.t. all operations have the same `score`.
private int maxOperations(int[] nums, int i, int j, int score, Map<String, Integer> mem) {
if (i >= j)
return 0;
final String key = hash(i, j, score);
if (mem.containsKey(key))
return mem.get(key);
final int deleteFirstTwo =
nums[i] + nums[i + 1] == score ? 1 + maxOperations(nums, i + 2, j, score, mem) : 0;
final int deleteLastTwo =
nums[j] + nums[j - 1] == score ? 1 + maxOperations(nums, i, j - 2, score, mem) : 0;
final int deleteFirstAndLast =
nums[i] + nums[j] == score ? 1 + maxOperations(nums, i + 1, j - 1, score, mem) : 0;
mem.put(key, Math.max(Math.max(deleteFirstTwo, deleteLastTwo), deleteFirstAndLast));
return mem.get(key);
}
private String hash(int i, int j, int score) {
return i + "," + j + "," + score;
}
} // code provided by PROGIEZ
3040. Maximum Number of Operations With the Same Score II LeetCode Solution in Python
class Solution:
def maxOperations(self, nums: list[int]) -> int:
@functools.lru_cache(None)
def dp(i: int, j: int, score: int) -> int:
"""
Returns the maximum number of operations that can be performed for
nums[i..j], s.t. all operations have the same `score`.
"""
if i >= j:
return 0
deleteFirstTwo = (1 + dp(i + 2, j, score)
if nums[i] + nums[i + 1] == score else 0)
deleteLastTwo = (1 + dp(i, j - 2, score)
if nums[j] + nums[j - 1] == score else 0)
deleteFirstAndLast = (1 + dp(i + 1, j - 1, score)
if nums[i] + nums[j] == score else 0)
return max(deleteFirstTwo, deleteLastTwo, deleteFirstAndLast)
n = len(nums)
return max(dp(0, n - 1, nums[0] + nums[1]),
dp(0, n - 1, nums[-1] + nums[-2]),
dp(0, n - 1, nums[0] + nums[-1])) # code by PROGIEZ
