2024-07-24：用go语言，给定一个整数数组 nums，其中至少包含两

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.在函数中，创建了一个长度为数组长度的二维 memo 数组，用于记忆化搜索。

maxOperations

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完整代码如下：

packagemain
import(
"fmt"
)
funcmaxOperations(nums[]int)int{
n:=len(nums)
memo:=make([][]int,n)
helper:=func(i,j,targetint)int{
fori:=rangememo{
memo[i]=make([]int,n)
forj:=rangememo[i]{
memo[i][j]=-1
}
}
vardfsfunc(int,int)int
dfs=func(i,jint)int{
ifi>=j{
return0
}
ifmemo[i][j]!=-1{
returnmemo[i][j]
}
ans:=0
ifnums[i]+nums[i+1]==target{
ans=max(ans,1+dfs(i+2,j))
}
ifnums[j-1]+nums[j]==target{
ans=max(ans,1+dfs(i,j-2))
}
ifnums[i]+nums[j]==target{
ans=max(ans,1+dfs(i+1,j-1))
}
memo[i][j]=ans
returnans
}
returndfs(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]))
returnres
}
funcmain(){
nums:=[]int{3,2,6,1,4}
fmt.Println(maxOperations(nums))
}