class Solution {
public:
int maxOperations(vector<int>& nums) {
}
};
100220. 相同分数的最大操作数目 II
给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：
nums 中最前面两个元素并且删除它们。nums 中最后两个元素并且删除它们。nums 中第一个和最后一个元素并且删除它们。一次操作的 分数 是被删除元素的和。
在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。
示例 1：
输入：nums = [3,2,1,2,3,4] 输出：3 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。 - 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。 - 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。 由于 nums 为空，我们无法继续进行任何操作。
示例 2：
输入：nums = [3,2,6,1,4] 输出：2 解释：我们执行以下操作： - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。 - 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。 至多进行 2 次操作。
提示：
2 <= nums.length <= 20001 <= nums[i] <= 1000原站题解
java 解法, 执行用时: 154 ms, 内存消耗: 77 MB, 提交时间: 2024-06-08 09:09:36
public class Solution {
public int maxOperations(int[] nums) {
int n = nums.length;
int res1 = helper(nums, 2, n - 1, nums[0] + nums[1]); // 删除前两个数
int res2 = helper(nums, 0, n - 3, nums[n - 2] + nums[n - 1]); // 删除后两个数
int res3 = helper(nums, 1, n - 2, nums[0] + nums[n - 1]); // 删除第一个和最后一个数
return Math.max(res1, Math.max(res2, res3)) + 1; // 加上第一次操作
}
private int helper(int[] nums, int start, int end, int target) {
int n = nums.length;
int[][] f = new int[n + 1][n + 1];
for (int i = end - 1; i >= start; i--) {
for (int j = i + 1; j <= end; j++) {
if (nums[i] + nums[i + 1] == target) { // 删除前两个数
f[i][j + 1] = Math.max(f[i][j + 1], f[i + 2][j + 1] + 1);
}
if (nums[j - 1] + nums[j] == target) { // 删除后两个数
f[i][j + 1] = Math.max(f[i][j + 1], f[i][j - 1] + 1);
}
if (nums[i] + nums[j] == target) { // 删除第一个和最后一个数
f[i][j + 1] = Math.max(f[i][j + 1], f[i + 1][j] + 1);
}
}
}
return f[start][end + 1];
}
}
python3 解法, 执行用时: 6849 ms, 内存消耗: 81 MB, 提交时间: 2024-06-08 09:09:20
class Solution:
def maxOperations(self, nums: List[int]) -> int:
def helper(start: int, end: int, target: int) -> int:
max = lambda a, b: b if b > a else a # 手写 max
f = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(end - 1, start - 1, -1):
for j in range(i + 1, end + 1):
res = 0
if nums[i] + nums[i + 1] == target: # 删除前两个数
res = max(res, f[i + 2][j + 1] + 1)
if nums[j - 1] + nums[j] == target: # 删除后两个数
res = max(res, f[i][j - 1] + 1)
if nums[i] + nums[j] == target: # 删除第一个和最后一个数
res = max(res, f[i + 1][j] + 1)
f[i][j + 1] = res
return f[start][end + 1]
n = len(nums)
res1 = helper(2, n - 1, nums[0] + nums[1]) # 删除前两个数
res2 = helper(0, n - 3, nums[-2] + nums[-1]) # 删除后两个数
res3 = helper(1, n - 2, nums[0] + nums[-1]) # 删除第一个和最后一个数
return max(res1, res2, res3) + 1 # 加上第一次操作
golang 解法, 执行用时: 155 ms, 内存消耗: 56.4 MB, 提交时间: 2024-06-08 09:09:00
func maxOperations(nums []int) int {
n := len(nums)
res1 := helper(nums[2:n], nums[0]+nums[1]) // 删除前两个数
res2 := helper(nums[:n-2], nums[n-2]+nums[n-1]) // 删除后两个数
res3 := helper(nums[1:n-1], nums[0]+nums[n-1]) // 删除第一个和最后一个数
return max(res1, res2, res3) + 1 // 加上第一次操作
}
func helper(a []int, target int) int {
n := len(a)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if a[i]+a[i+1] == target { // 删除前两个数
f[i][j+1] = max(f[i][j+1], f[i+2][j+1]+1)
}
if a[j-1]+a[j] == target { // 删除后两个数
f[i][j+1] = max(f[i][j+1], f[i][j-1]+1)
}
if a[i]+a[j] == target { // 删除第一个和最后一个数
f[i][j+1] = max(f[i][j+1], f[i+1][j]+1)
}
}
}
return f[0][n]
}
cpp 解法, 执行用时: 550 ms, 内存消耗: 144.2 MB, 提交时间: 2024-06-08 09:08:12
class Solution {
public:
int maxOperations(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> memo(n, vector<int>(n));
auto helper = [&](int i, int j, int target) -> int {
for (auto& row : memo) {
ranges::fill(row, -1); // -1 表示没有计算过
}
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (i >= j) return 0;
int& res = memo[i][j]; // 注意这里是引用
if (res != -1) return res; // 之前计算过
res = 0;
if (nums[i] + nums[i + 1] == target) res = max(res, dfs(i + 2, j) + 1);
if (nums[j - 1] + nums[j] == target) res = max(res, dfs(i, j - 2) + 1);
if (nums[i] + nums[j] == target) res = max(res, dfs(i + 1, j - 1) + 1);
return res;
};
return dfs(i, j);
};
int res1 = helper(2, n - 1, nums[0] + nums[1]); // 删除前两个数
int res2 = helper(0, n - 3, nums[n - 2] + nums[n - 1]); // 删除后两个数
int res3 = helper(1, n - 2, nums[0] + nums[n - 1]); // 删除第一个和最后一个数
return max({res1, res2, res3}) + 1; // 加上第一次操作
}
};
java 解法, 执行用时: 154 ms, 内存消耗: 75.6 MB, 提交时间: 2024-02-19 14:45:19
class Solution {
private int[] nums;
private int[][] memo;
public int maxOperations(int[] nums) {
int n = nums.length;
this.nums = nums;
memo = new int[n][n];
int res1 = helper(2, n - 1, nums[0] + nums[1]); // 最前面两个
int res2 = helper(0, n - 3, nums[n - 2] + nums[n - 1]); // 最后两个
int res3 = helper(1, n - 2, nums[0] + nums[n - 1]); // 第一个和最后一个
return Math.max(Math.max(res1, res2), res3) + 1; // 加上第一次操作
}
private int helper(int i, int j, int target) {
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(i, j, target);
}
private int dfs(int i, int j, int target) {
if (i >= j) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
int res = 0;
if (nums[i] + nums[i + 1] == target) {
res = Math.max(res, dfs(i + 2, j, target) + 1);
}
if (nums[j - 1] + nums[j] == target) {
res = Math.max(res, dfs(i, j - 2, target) + 1);
}
if (nums[i] + nums[j] == target) {
res = Math.max(res, dfs(i + 1, j - 1, target) + 1);
}
return memo[i][j] = res;
}
}
python3 解法, 执行用时: 2131 ms, 内存消耗: 377.6 MB, 提交时间: 2024-02-19 14:45:05
class Solution:
def maxOperations(self, nums: List[int]) -> int:
@cache
def dfs(i: int, j: int, target: int) -> int:
if i >= j:
return 0
res = 0
if nums[i] + nums[i + 1] == target: # 最前面两个
res = max(res, dfs(i + 2, j, target) + 1)
if nums[j - 1] + nums[j] == target: # 最后两个
res = max(res, dfs(i, j - 2, target) + 1)
if nums[i] + nums[j] == target: # 第一个和最后一个
res = max(res, dfs(i + 1, j - 1, target) + 1)
return res
n = len(nums)
res1 = dfs(2, n - 1, nums[0] + nums[1]) # 最前面两个
res2 = dfs(0, n - 3, nums[-2] + nums[-1]) # 最后两个
res3 = dfs(1, n - 2, nums[0] + nums[-1]) # 第一个和最后一个
return max(res1, res2, res3) + 1 # 加上第一次操作
golang 解法, 执行用时: 196 ms, 内存消耗: 65.5 MB, 提交时间: 2024-02-19 14:44:50
// 由于只能从两端删除，所以子问题是「从两侧向内缩小的」，使用区间 DP 解决。
func maxOperations(nums []int) int {
n := len(nums)
res1 := helper(nums[2:], nums[0]+nums[1]) // 最前面两个
res2 := helper(nums[:n-2], nums[n-2]+nums[n-1]) // 最后两个
res3 := helper(nums[1:n-1], nums[0]+nums[n-1]) // 第一个和最后一个
return max(res1, res2, res3) + 1 // 加上第一次操作
}
func helper(a []int, target int) int {
n := len(a)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int) int // dfs(i, j) 当剩下元素nums[i..j], 最多可进行的操作次数
dfs = func(i, j int) (res int) {
if i >= j {
return
}
p := &memo[i][j]
if *p != -1 {
return *p
}
if a[i]+a[i+1] == target { // 最前面两个
res = max(res, dfs(i+2, j)+1)
}
if a[j-1]+a[j] == target { // 最后两个
res = max(res, dfs(i, j-2)+1)
}
if a[i]+a[j] == target { // 第一个和最后一个
res = max(res, dfs(i+1, j-1)+1)
}
*p = res
return
}
return dfs(0, n-1)
}