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

package mainimport ("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 { return 0 } 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 := 0res = 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))}