題目難度：中等

主要提升：for循環思想、動態規劃思想、數組操作

一、題目描述：

給你一個整數數組?nums?，如果?nums?至少包含?2?個元素，你可以執行以下操作中的任意一個：
（1）選擇?nums?中最前面兩個元素并且刪除它們。
（2）選擇?nums?中最后兩個元素并且刪除它們。
（3）選擇?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 次操作。

三、思路：

要使用動態規劃的思想，對于三種情況分別進行計算，返回最優解為最大次數。

四、代碼：

參考Leetcode：

class Solution {int[] nums;int[][] memo;public int maxOperations(int[] nums) {// 初始化變量int n = nums.length; // 獲取輸入數組的長度this.nums = nums; // 將輸入數組賦值給類的成員變量this.memo = new int[n][n]; // 創建一個二維數組用于記憶化搜索int res = 0; // 初始化結果變量為0// 嘗試三種不同的操作并取最大值res = Math.max(res, helper(0, n - 1, nums[0] + nums[n - 1]));res = Math.max(res, helper(0, n - 1, nums[0] + nums[1]));res = Math.max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1]));return res; // 返回最終結果}public int helper(int i, int j, int target) {// 重置記憶化數組for (int k = 0; k < nums.length; k++) {Arrays.fill(memo[k], -1);}// 調用深度優先搜索函數return dfs(i, j, target);}public int dfs(int i, int j, int target) {// 遞歸終止條件if (i >= j) {return 0;}// 如果已經計算過這個子問題，直接返回記憶化的結果if (memo[i][j] != -1) {return memo[i][j];}// 初始化答案為0int ans = 0;// 檢查三種可能的操作if (nums[i] + nums[i + 1] == target) {ans = Math.max(ans, dfs(i + 2, j, target) + 1);}if (nums[j - 1] + nums[j] == target) {ans = Math.max(ans, dfs(i, j - 2, target) + 1);}if (nums[i] + nums[j] == target) {ans = Math.max(ans, dfs(i + 1, j - 1, target) + 1);}// 記憶化當前的結果memo[i][j] = ans;// 返回答案return ans;}
}