🔥 Maximum Number of Operations with the Same Score II | Optimized DP Solution 💡
IntuitionThe problem asks us to maximize the number of operations where pairs of elements in the array sum up to a specific value. To achieve this, we need to e
### Intuition  

The problem asks us to maximize the number of operations where pairs of elements in the array sum up to a specific value. To achieve this, we need to explore potential pair combinations and track valid operations efficiently. This can be solved using recursion with memoization (dynamic programming) to avoid redundant computations.

---

### Approach  

1. **Recursive Function:**  
   - Define a function `rec(l, r, sm)` where:
     - $$l$$: Left pointer.
     - $$r$$: Right pointer.
     - $$sm$$: Target sum for the current operation.
   - Base cases:
     - If $$l \geq r$$, no more pairs can be formed, return $$0$$.
     - If the result for $$dp[l][r]$$ is already computed, return it.

2. **Operations:**  
   - Check pairs that satisfy the sum $$sm$$:
     - Pair the first two elements: `nums[l] + nums[l+1]`.
     - Pair the first and last elements: `nums[l] + nums[r]`.
     - Pair the last two elements: `nums[r-1] + nums[r]`.
   - Recur for the remaining array after removing the pair.

3. **Optimization with Memoization:**  
   - Use a 2D `dp` table to store intermediate results and avoid redundant calculations.

4. **Initial Calls:**  
   - Try all possible sums formed by the first two, first and last, or last two elements as initial target sums.

5. **Result:**  
   - The final answer is the maximum number of operations across all possible initial target sums.

---

### Complexity  

- **Time Complexity:**  
  - $$O(n^2)$$: We solve at most $$O(n^2)$$ subproblems, each taking $$O(1)$$.  
- **Space Complexity:**  
  - $$O(n^2)$$: Space required for the 2D `dp` table and recursion stack.

---

### Code  

```cpp
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size();
        vector dp(n, vector(n, 0)); // DP table
        vector t(n, vector(n, 0)); // Temporary table
        
        // Recursive function
        auto rec = [&](auto&& rec, int l, int r, int sm) -> int {
            if (l == 0 && r == n - 1) dp = t; // Reset DP for new target sum
            if (l >= r) return 0; // Base case: no pairs possible
            if (dp[l][r]) return dp[l][r]; // Use memoized result
            
            int mx = 0; // Maximum operations
            if (nums[l] + nums[l + 1] == sm)
                mx = max(mx, rec(rec, l + 2, r, sm) + 1);
            if (nums[l] + nums[r] == sm)
                mx = max(mx, rec(rec, l + 1, r - 1, sm) + 1);
            if (nums[r] + nums[r - 1] == sm)
                mx = max(mx, rec(rec, l, r - 2, sm) + 1);
            
            return dp[l][r] = mx; // Store result
        };
        
        // Try all possible initial target sums
        int ans = max({
            rec(rec, 0, n - 1, nums[0] + nums[1]),
            rec(rec, 0, n - 1, nums[0] + nums[n - 1]),
            rec(rec, 0, n - 1, nums[n - 1] + nums[n - 2])
        });
        
        return ans;
    }
};
```

---

### Example  

**Input:**  
`nums = [3, 2, 3, 4, 3]`  

**Execution:**  
- Possible target sums are:
  - $$nums[0] + nums[1] = 5$$.
  - $$nums[0] + nums[4] = 6$$.
  - $$nums[3] + nums[4] = 7$$.
- For each target sum:
  - Use recursive function `rec` to calculate the maximum operations.
- The maximum number of operations is returned.

**Output:**  
```plaintext
2
```

---

### Edge Cases  

1. **Single Element:**  
   `nums = [1]` → `0` (No pairs possible).  

2. **All Elements Are Equal:**  
   `nums = [2, 2, 2, 2]` → Maximum pairs depend on the sum of two elements.  

3. **No Valid Pairs:**  
   `nums = [1, 3, 5]` → `0` (No pairs matching any target sum).  

---

### Key Insights  

- Efficiently handle pair combinations using recursion and memoization.  
- Test different initial target sums for the most optimal solution.  
- Ensure edge cases are covered for robustness.  
['Array', 'Two Pointers', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']