2024-07-24：用 go 语言，给定一个整数数组 nums，其中至少包含两个元素。可以根据以下规则执行操作：选择最前面两个元素删除、选择最后两个元素删除，或选择第一个和最后一个元素删除。每次操作

作者：福大大架构师每日一题

2024-07-24
北京
本文字数：1299 字
阅读完需：约 4 分钟

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 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 {                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 := 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))}