# Maximum Number of Operations With the Same Score II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-operations-with-the-same-score-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-operations-with-the-same-score-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Array
---
## Problem
Given an array of integers called `nums`, you can perform **any** of the following operation while `nums` contains **at least** `2` elements:

* Choose the first two elements of `nums` and delete them.
* Choose the last two elements of `nums` and delete them.
* Choose the first and the last elements of `nums` and delete them.

The **score** of the operation is the sum of the deleted elements.

Your task is to find the **maximum** number of operations that can be performed, such that **all operations have the same score**.

Return _the **maximum** number of operations possible that satisfy the condition mentioned above_.

**Example 1:**

**Input:** nums = [3,2,1,2,3,4]
**Output:** 3
**Explanation:** We perform the following operations:
- Delete the first two elements, with score 3 + 2 = 5, nums = [1,2,3,4].
- Delete the first and the last elements, with score 1 + 4 = 5, nums = [2,3].
- Delete the first and the last elements, with score 2 + 3 = 5, nums = [].
We are unable to perform any more operations as nums is empty.

**Example 2:**

**Input:** nums = [3,2,6,1,4]
**Output:** 2
**Explanation:** We perform the following operations:
- Delete the first two elements, with score 3 + 2 = 5, nums = [6,1,4].
- Delete the last two elements, with score 1 + 4 = 5, nums = [6].
It can be proven that we can perform at most 2 operations.

**Constraints:**

* `2 <= nums.length <= 2000`
* `1 <= nums[i] <= 1000`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's recursive nature into code. We identify that the first operation determines the target score for all subsequent operations. There are three possible first moves, leading to three potential target scores. For each target score, we can define a recursive function that explores all possible sequences of operations. The state of the recursion can be defined by the start and end indices of the current subarray. The function tries all three types of operations (from the front, from the back, from both ends) and recursively calls itself on the smaller subarray, taking the path that yields the maximum number of operations.
**Time:** O(3^(n/2)) - In the worst-case scenario, each recursive call can branch into three further calls. The depth of the recursion is roughly `n/2`. This leads to an exponential number of function calls, making it too slow for the given constraints. · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can be up to `n/2` in the worst case.
**Pros:** Simple to conceptualize and implement.; Directly models the decision-making process described in the problem.
**Cons:** Highly inefficient due to the re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The main function `maxOperations` considers three initial scenarios:
1.  Removing `nums[0]` and `nums[1]`. The score is `nums[0] + nums[1]`. We get 1 operation plus whatever we can get from the rest of the array `nums[2...n-1]`.
2.  Removing `nums[n-2]` and `nums[n-1]`. The score is `nums[n-2] + nums[n-1]`. We get 1 operation plus the result from `nums[0...n-3]`.
3.  Removing `nums[0]` and `nums[n-1]`. The score is `nums[0] + nums[n-1]`. We get 1 operation plus the result from `nums[1...n-2]`.

A helper function `solve(nums, start, end, score)` is implemented to handle the recursive calculation. It returns the maximum number of operations possible on the subarray `nums[start...end]` for a fixed `score`. In each call, it checks all three possible moves. If a move's sum matches the target `score`, it makes a recursive call for the resulting subproblem and adds 1 (for the current operation). The function returns the maximum value among all valid moves.

```java
class Solution {
    public int maxOperations(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        
        int maxOps = 0;
        
        // Case 1: Remove first two elements
        maxOps = Math.max(maxOps, 1 + solve(nums, 2, n - 1, nums[0] + nums[1]));
        
        // Case 2: Remove last two elements
        maxOps = Math.max(maxOps, 1 + solve(nums, 0, n - 3, nums[n - 1] + nums[n - 2]));
        
        // Case 3: Remove first and last elements
        maxOps = Math.max(maxOps, 1 + solve(nums, 1, n - 2, nums[0] + nums[n - 1]));
        
        return maxOps;
    }

    private int solve(int[] nums, int start, int end, int score) {
        if (start >= end) {
            return 0;
        }
        
        int res = 0;
        
        // Option 1: remove from front
        if (nums[start] + nums[start + 1] == score) {
            res = Math.max(res, 1 + solve(nums, start + 2, end, score));
        }
        
        // Option 2: remove from back
        if (nums[end] + nums[end - 1] == score) {
            res = Math.max(res, 1 + solve(nums, start, end - 2, score));
        }
        
        // Option 3: remove from both ends
        if (nums[start] + nums[end] == score) {
            res = Math.max(res, 1 + solve(nums, start + 1, end - 1, score));
        }
        
        return res;
    }
}
```
### Algorithm
- The problem can be broken down into three main scenarios based on the first operation:
    a. Removing the first two elements (`nums[0]`, `nums[1]`)
    b. Removing the last two elements (`nums[n-1]`, `nums[n-2]`)
    c. Removing the first and last elements (`nums[0]`, `nums[n-1]`)
- The sum of the elements removed in the first operation becomes the target `score` for all subsequent operations.
- We define a recursive helper function, say `solve(start, end, score)`, which calculates the maximum number of operations for the subarray `nums[start...end]` with the given `score`.
- Inside `solve(start, end, score)`:
    - **Base Case:** If `start >= end` (less than two elements left), return 0.
    - **Recursive Step:** Explore three possible moves:
        - If `nums[start] + nums[start+1] == score`, recursively call `1 + solve(start+2, end, score)`.
        - If `nums[end] + nums[end-1] == score`, recursively call `1 + solve(start, end-2, score)`.
        - If `nums[start] + nums[end] == score`, recursively call `1 + solve(start+1, end-1, score)`.
- The result for the current state is the maximum of the outcomes of the valid moves. If no move is valid, return 0.
- The final answer is the maximum result obtained from the three initial scenarios.

## Dynamic Programming with Memoization
The brute-force recursive approach is inefficient because it repeatedly solves the same subproblems. For a given target score, the maximum number of operations for a subarray `nums[start...end]` is always the same, yet the naive recursion calculates it multiple times. We can significantly optimize this by using memoization, a top-down dynamic programming technique. We store the result of each subproblem `(start, end)` in a 2D cache (or memoization table). When the function is called for a subproblem, it first checks the cache. If the result is present, it's returned instantly, avoiding redundant computation. If not, the result is computed, stored in the cache, and then returned.
**Time:** O(n^2) - There are `O(n^2)` unique subproblems defined by `(start, end)`. Each subproblem is computed only once. The computation within each call is constant time. Since we run this process for three different initial scores, the total time complexity is `3 * O(n^2)`, which simplifies to `O(n^2)`. · **Space:** O(n^2) - The space is dominated by the `n x n` memoization table. The recursion stack depth contributes an additional O(n) space.
**Pros:** Efficient and optimal for the given constraints.; Avoids re-computation of subproblems, drastically reducing the time complexity from exponential to polynomial.; It is a standard and powerful technique for problems with optimal substructure and overlapping subproblems.
**Cons:** Requires O(n^2) extra space for the memoization table, which might be a concern for extremely large constraints on `n`.
### Explanation
This approach enhances the recursive solution by adding a memoization table, typically a 2D array `memo`, to store the results of subproblems. The state `(start, end)` maps to `memo[start][end]`. We need a separate memoization context for each of the three initial scores, so we'll call a helper function three times, each with its own memoization table.

The helper function `solve(nums, start, end, score, memo)` first checks if `memo[start][end]` contains a pre-computed result. If it does, it returns that value. Otherwise, it calculates the result by exploring the three possible moves, just like in the brute-force version. The key difference is that before returning the calculated result, it stores it in `memo[start][end]`. This ensures that for any given `score`, the subproblem for `(start, end)` is solved only once.

```java
class Solution {
    public int maxOperations(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        
        int maxOps = 0;
        
        // Case 1: Remove first two elements
        int score1 = nums[0] + nums[1];
        Integer[][] memo1 = new Integer[n][n];
        maxOps = Math.max(maxOps, 1 + solve(nums, 2, n - 1, score1, memo1));
        
        // Case 2: Remove last two elements
        int score2 = nums[n - 1] + nums[n - 2];
        Integer[][] memo2 = new Integer[n][n];
        maxOps = Math.max(maxOps, 1 + solve(nums, 0, n - 3, score2, memo2));
        
        // Case 3: Remove first and last elements
        int score3 = nums[0] + nums[n - 1];
        Integer[][] memo3 = new Integer[n][n];
        maxOps = Math.max(maxOps, 1 + solve(nums, 1, n - 2, score3, memo3));
        
        return maxOps;
    }

    private int solve(int[] nums, int start, int end, int score, Integer[][] memo) {
        if (start >= end) {
            return 0;
        }
        if (memo[start][end] != null) {
            return memo[start][end];
        }
        
        int res = 0;
        
        // Option 1: remove from front
        if (nums[start] + nums[start + 1] == score) {
            res = Math.max(res, 1 + solve(nums, start + 2, end, score, memo));
        }
        
        // Option 2: remove from back
        if (nums[end] + nums[end - 1] == score) {
            res = Math.max(res, 1 + solve(nums, start, end - 2, score, memo));
        }
        
        // Option 3: remove from both ends
        if (nums[start] + nums[end] == score) {
            res = Math.max(res, 1 + solve(nums, start + 1, end - 1, score, memo));
        }
        
        return memo[start][end] = res;
    }
}
```
### Algorithm
- The core recursive structure remains the same as the brute-force approach. The state is defined by `(start, end)`.
- We introduce a 2D array, `memo[n][n]`, to store the results of the `solve(start, end)` function for a fixed score. A separate memoization table is used for each of the three initial score possibilities.
- The helper function is modified to `solve(start, end, score, memo)`.
- Before computing the result for a state `(start, end)`, we first check if `memo[start][end]` has already been computed (e.g., it's not `null`). If so, we return the stored value immediately.
- If the result is not in the memoization table, we compute it recursively as in the brute-force approach.
- After computing the result, we store it in `memo[start][end]` before returning it.
- The main function initializes three separate memoization tables and calls the helper function for each of the three initial scenarios.

# Solutions
### Java

```java
class Solution {
private
  Integer[][] f;
private
  int[] nums;
private
  int s;
private
  int n;
public
  int maxOperations(int[] nums) {
    this.nums = nums;
    n = nums.length;
    int a = g(2, n - 1, nums[0] + nums[1]);
    int b = g(0, n - 3, nums[n - 2] + nums[n - 1]);
    int c = g(1, n - 2, nums[0] + nums[n - 1]);
    return 1 + Math.max(a, Math.max(b, c));
  }
private
  int g(int i, int j, int s) {
    f = new Integer[n][n];
    this.s = s;
    return dfs(i, j);
  }
private
  int dfs(int i, int j) {
    if (j - i < 1) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = 0;
    if (nums[i] + nums[i + 1] == s) {
      ans = Math.max(ans, 1 + dfs(i + 2, j));
    }
    if (nums[i] + nums[j] == s) {
      ans = Math.max(ans, 1 + dfs(i + 1, j - 1));
    }
    if (nums[j - 1] + nums[j] == s) {
      ans = Math.max(ans, 1 + dfs(i, j - 2));
    }
    return f[i][j] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxOperations(vector<int> &nums) {
    int n = nums.size();
    int f[n][n];
    auto g = [&](int i, int j, int s) -> int {
      memset(f, -1, sizeof(f));
      function<int(int, int)> dfs = [&](int i, int j) -> int {
        if (j - i < 1) {
          return 0;
        }
        if (f[i][j] != -1) {
          return f[i][j];
        }
        int ans = 0;
        if (nums[i] + nums[i + 1] == s) {
          ans = max(ans, 1 + dfs(i + 2, j));
        }
        if (nums[i] + nums[j] == s) {
          ans = max(ans, 1 + dfs(i + 1, j - 1));
        }
        if (nums[j - 1] + nums[j] == s) {
          ans = max(ans, 1 + dfs(i, j - 2));
        }
        return f[i][j] = ans;
      };
      return dfs(i, j);
    };
    int a = g(2, n - 1, nums[0] + nums[1]);
    int b = g(0, n - 3, nums[n - 2] + nums[n - 1]);
    int c = g(1, n - 2, nums[0] + nums[n - 1]);
    return 1 + max({a, b, c});
  }
};

```

### Python

```python
class Solution:
    def maxOperations(self, nums: List[int]) -> int: @ cache def dfs(i: int, j: int, s: int) -> int: if j - i < 1: return 0 ans = 0 if nums[i] + nums[i + 1] == s: ans = max(ans, 1 + dfs(i + 2, j, s)) if nums[i] + nums[j] == s: ans = max(ans, 1 + dfs(i + 1, j - 1, s)) if nums[j - 1] + nums[j] == s: ans = max(ans, 1 + dfs(i, j - 2, s)) return ans n = len(nums) a = dfs(2, n - 1, nums[0] + nums[1]) b = dfs(0, n - 3, nums[- 1] + nums[- 2]) c = dfs(1, n - 2, nums[0] + nums[- 1]) return 1 + max(a, b, c)

```