说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个整数数组 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
解题思路
直接深搜3种取值的操作次数：
- 选择
nums中最前面两个元素并且删除它们。
dfs(nums[0] + nums[1], 2, nums.length - 1);
- 选择
nums中最后两个元素并且删除它们。
dfs(nums[0] + nums[nums.length - 1], 1, nums.length - 2);
- 选择
nums中第一个和最后一个元素并且删除它们。
dfs(nums[nums.length - 1] + nums[nums.length - 2], 0, nums.length - 3);
深搜过程中也分别计算不同取值的最大操作次数
const dfs = (sum, left, right, cnt = 1) => { if (map[left + "-" + right]) return 0; if (left >= right) return cnt; let t1 = (t2 = t3 = 0); if (nums[left] + nums[left + 1] === sum) t1 = dfs(sum, left + 2, right, cnt + 1); if (nums[left] + nums[right] === sum) t2 = dfs(sum, left + 1, right - 1, cnt + 1); if (nums[right] + nums[right - 1] === sum) t3 = dfs(sum, left, right - 2, cnt + 1); cnt = Math.max(t1, t2, t3, cnt); map[left + "-" + right] = true; maxCnt = Math.max(maxCnt, cnt); return cnt; };
- 快速处理元素相同的数组
如果数组中的所有元素都是相同的话，那么他的最大操作次数为：Math.floor(sortNums.length / 2)
const sortNums = [...nums].sort((a, b) => a - b); if (sortNums[0] === sortNums[sortNums.length - 1]) return Math.floor(sortNums.length / 2);
AC代码
/** * @param {number[]} nums * @return {number} */ var maxOperations = function (nums) { const map = {}; let maxCnt = 1; const dfs = (sum, left, right, cnt = 1) => { if (map[left + "-" + right]) return 0; if (left >= right) return cnt; let t1 = (t2 = t3 = 0); if (nums[left] + nums[left + 1] === sum) t1 = dfs(sum, left + 2, right, cnt + 1); if (nums[left] + nums[right] === sum) t2 = dfs(sum, left + 1, right - 1, cnt + 1); if (nums[right] + nums[right - 1] === sum) t3 = dfs(sum, left, right - 2, cnt + 1); cnt = Math.max(t1, t2, t3, cnt); map[left + "-" + right] = true; maxCnt = Math.max(maxCnt, cnt); return cnt; }; const sortNums = [...nums].sort((a, b) => a - b); if (sortNums[0] === sortNums[sortNums.length - 1]) return Math.floor(sortNums.length / 2); dfs(nums[0] + nums[1], 2, nums.length - 1); dfs(nums[0] + nums[nums.length - 1], 1, nums.length - 2); dfs(nums[nums.length - 1] + nums[nums.length - 2], 0, nums.length - 3); return maxCnt; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
