2024-07-24：用go语言，给定一个整数数组 nums，其中至少包含两个元素。
可以根据以下规则执行操作：选择最前面两个元素删除、选择最后两个元素删除，或选择第一个和最后一个元素删除。
每次操作的得分是被删除元素的和。
在每次操作后，所有操作得分需保持相同。
问题要求确定在这些前提下，最多可以进行多少次操作。
最终需要返回可进行的最大操作次数。
输入：nums = [3,2,6,1,4]。
输出：2。
解释：我们执行以下操作：
删除前两个元素，分数为 3 2 = 5 ，nums = [6,1,4] 。
删除最后两个元素，分数为 1 4 = 5 ，nums = [6] 。
至多进行 2 次操作。
答案2024-07-24：
chatgpt
题目来自leetcode3040。
大体步骤如下：
1.程序定义了一个 maxOperations 函数，其中传入一个整数数组 nums，函数返回最大操作次数。
2.在 maxOperations 函数中，创建了一个长度为数组长度的二维 memo 数组，用于记忆化搜索。
3.定义了一个内部帮助函数 helper，实现了动态规划解决问题的过程。
4.在 helper 函数中，通过递归实现每次操作的得分计算，以及记录每次操作的得分情况，并最终返回最大操作次数。
5.主要操作包括选择删除开头两个元素，删除末尾两个元素，或者删除第一个和最后一个元素三种情况。
6.在主函数中，给定了一个示例数组 [3,2,6,1,4]，并输出了最大操作次数。
总的时间复杂度：
- • 定义 memo 数组时的时间复杂度：O(n^2)
- • 递归计算操作得分的时间复杂度：O(n^2)
- • 总体时间复杂度为 O(n^2)
总的额外空间复杂度：
- • memo 数组的额外空间复杂度为 O(n^2)，用于记忆化搜索。
- • 递归调用过程中的栈空间开销不考虑。
- • 总体额外空间复杂度为 O(n^2)。
Go完整代码如下：
代码语言：javascript复制package main
import(
"fmt"
)
func maxOperations(nums []int)int{
n :=len(nums)
memo :=make([][]int, n)
helper :=func(i, j, target int)int{
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 =func(i, j int)int{
if i >= j {
return0
}
if memo[i][j]!=-1{
return memo[i][j]
}
ans :=0
if nums[i] nums[i 1]== target {
ans = max(ans,1 dfs(i 2, j))
}
if nums[j -1] nums[j]== target {
ans = max(ans,1 dfs(i, j -2))
}
if nums[i] nums[j]== target {
ans = max(ans,1 dfs(i 1, j -1))
}
memo[i][j]= ans
return ans
}
return dfs(i, j)
}
res :=0
res = max(res, helper(0, n -1, nums[0] nums[n -1]))
res = max(res, helper(0, n -1, nums[0] nums[1]))
res = max(res, helper(0, n -1, nums[n -2] nums[n -1]))
return res
}
func main(){
nums:=[]int{3,2,6,1,4}
fmt.Println(maxOperations(nums))
}
