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.

Thescore 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 themaximum number of operations possible that satisfy the condition mentioned above.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6

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

Solution

Method 1 – DP with Memoization (Try All Splits)

Intuition

At each step, you can remove the first two, last two, or first and last elements. The score for each operation must be the same. Try all possible first moves, then recursively check if you can continue with the same score. Use memoization to avoid recomputation.

Approach

  1. For all possible ways to remove two elements at the start, end, or both, compute the score and recursively try to maximize the number of operations with that score.
  2. Use memoization to cache results for (left, right, score).
  3. For each possible initial operation, recursively try all valid next operations with the same score.
  4. Return the maximum number of operations found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        function<int(int, int, int)> dfs = [&](int l, int r, int score) {
            if (r - l + 1 < 2) return 0;
            int res = 0;
            if (l + 1 <= r && nums[l] + nums[l+1] == score)
                res = max(res, 1 + dfs(l+2, r, score));
            if (r - 1 >= l && nums[r] + nums[r-1] == score)
                res = max(res, 1 + dfs(l, r-2, score));
            if (l < r && nums[l] + nums[r] == score)
                res = max(res, 1 + dfs(l+1, r-1, score));
            return res;
        };
        if (n < 2) return 0;
        ans = max(ans, 1 + dfs(2, n-1, nums[0] + nums[1]));
        ans = max(ans, 1 + dfs(0, n-3, nums[n-1] + nums[n-2]));
        ans = max(ans, 1 + dfs(1, n-2, nums[0] + nums[n-1]));
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

func maxOperations(nums []int) int {
    n := len(nums)
    if n < 2 {
        return 0
    }
    
    // Memoization map
    memo := make(map[string]int)
    
    var dfs func(l, r, score int) int
    dfs = func(l, r, score int) int {
        if r-l+1 < 2 {
            return 0
        }
        
        key := fmt.Sprintf("%d,%d,%d", l, r, score)
        if val, exists := memo[key]; exists {
            return val
        }
        
        res := 0
        
        // Try removing first two elements
        if l+1 <= r && nums[l]+nums[l+1] == score {
            res = max(res, 1+dfs(l+2, r, score))
        }
        
        // Try removing last two elements
        if r-1 >= l && nums[r]+nums[r-1] == score {
            res = max(res, 1+dfs(l, r-2, score))
        }
        
        // Try removing first and last elements
        if l < r && nums[l]+nums[r] == score {
            res = max(res, 1+dfs(l+1, r-1, score))
        }
        
        memo[key] = res
        return res
    }
    
    ans := 0
    
    // Try all three possible first operations
    ans = max(ans, 1+dfs(2, n-1, nums[0]+nums[1]))           // Remove first two
    ans = max(ans, 1+dfs(0, n-3, nums[n-1]+nums[n-2]))       // Remove last two
    ans = max(ans, 1+dfs(1, n-2, nums[0]+nums[n-1]))         // Remove first and last
    
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    private int[] nums;
    
    public int maxOperations(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        if (n < 2) return 0;
        
        int ans = 0;
        
        // Try all three possible first operations
        ans = Math.max(ans, 1 + dfs(2, n - 1, nums[0] + nums[1]));           // Remove first two
        ans = Math.max(ans, 1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2]));   // Remove last two
        ans = Math.max(ans, 1 + dfs(1, n - 2, nums[0] + nums[n - 1]));       // Remove first and last
        
        return ans;
    }
    
    private int dfs(int l, int r, int score) {
        if (r - l + 1 < 2) {
            return 0;
        }
        
        String key = l + "," + r + "," + score;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int res = 0;
        
        // Try removing first two elements
        if (l + 1 <= r && nums[l] + nums[l + 1] == score) {
            res = Math.max(res, 1 + dfs(l + 2, r, score));
        }
        
        // Try removing last two elements
        if (r - 1 >= l && nums[r] + nums[r - 1] == score) {
            res = Math.max(res, 1 + dfs(l, r - 2, score));
        }
        
        // Try removing first and last elements
        if (l < r && nums[l] + nums[r] == score) {
            res = Math.max(res, 1 + dfs(l + 1, r - 1, score));
        }
        
        memo.put(key, res);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import kotlin.math.max

class Solution {
    private val memo = mutableMapOf<String, Int>()
    private lateinit var nums: IntArray
    
    fun maxOperations(nums: IntArray): Int {
        this.nums = nums
        val n = nums.size
        if (n < 2) return 0
        
        var ans = 0
        
        // Try all three possible first operations
        ans = max(ans, 1 + dfs(2, n - 1, nums[0] + nums[1]))           // Remove first two
        ans = max(ans, 1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2]))   // Remove last two
        ans = max(ans, 1 + dfs(1, n - 2, nums[0] + nums[n - 1]))       // Remove first and last
        
        return ans
    }
    
    private fun dfs(l: Int, r: Int, score: Int): Int {
        if (r - l + 1 < 2) {
            return 0
        }
        
        val key = "$l,$r,$score"
        if (key in memo) {
            return memo[key]!!
        }
        
        var res = 0
        
        // Try removing first two elements
        if (l + 1 <= r && nums[l] + nums[l + 1] == score) {
            res = max(res, 1 + dfs(l + 2, r, score))
        }
        
        // Try removing last two elements
        if (r - 1 >= l && nums[r] + nums[r - 1] == score) {
            res = max(res, 1 + dfs(l, r - 2, score))
        }
        
        // Try removing first and last elements
        if (l < r && nums[l] + nums[r] == score) {
            res = max(res, 1 + dfs(l + 1, r - 1, score))
        }
        
        memo[key] = res
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from functools import cache
class Solution:
    def maxOperations(self, nums: list[int]) -> int:
        n = len(nums)
        @cache
        def dfs(l: int, r: int, score: int) -> int:
            if r - l + 1 < 2:
                return 0
            res = 0
            if l + 1 <= r and nums[l] + nums[l+1] == score:
                res = max(res, 1 + dfs(l+2, r, score))
            if r - 1 >= l and nums[r] + nums[r-1] == score:
                res = max(res, 1 + dfs(l, r-2, score))
            if l < r and nums[l] + nums[r] == score:
                res = max(res, 1 + dfs(l+1, r-1, score))
            return res
        ans = 0
        if n < 2:
            return 0
        ans = max(ans, 1 + dfs(2, n-1, nums[0] + nums[1]))
##### Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

use std::collections::HashMap;

impl Solution {
    pub fn max_operations(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n < 2 {
            return 0;
        }
        
        let mut memo = HashMap::new();
        
        fn dfs(
            l: usize,
            r: usize,
            score: i32,
            nums: &Vec<i32>,
            memo: &mut HashMap<String, i32>,
        ) -> i32 {
            if r < l || r - l + 1 < 2 {
                return 0;
            }
            
            let key = format!("{},{},{}", l, r, score);
            if let Some(&val) = memo.get(&key) {
                return val;
            }
            
            let mut res = 0;
            
            // Try removing first two elements
            if l + 1 <= r && nums[l] + nums[l + 1] == score {
                res = res.max(1 + dfs(l + 2, r, score, nums, memo));
            }
            
            // Try removing last two elements
            if r >= 1 && r - 1 >= l && nums[r] + nums[r - 1] == score {
                res = res.max(1 + dfs(l, r - 2, score, nums, memo));
            }
            
            // Try removing first and last elements
            if l < r && nums[l] + nums[r] == score {
                res = res.max(1 + dfs(l + 1, r - 1, score, nums, memo));
            }
            
            memo.insert(key, res);
            res
        }
        
        let mut ans = 0;
        
        // Try all three possible first operations
        ans = ans.max(1 + dfs(2, n - 1, nums[0] + nums[1], &nums, &mut memo));               // Remove first two
        ans = ans.max(1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2], &nums, &mut memo));     // Remove last two
        ans = ans.max(1 + dfs(1, n - 2, nums[0] + nums[n - 1], &nums, &mut memo));         // Remove first and last
        
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

function maxOperations(nums: number[]): number {
    const n = nums.length;
    if (n < 2) return 0;
    
    const memo = new Map<string, number>();
    
    const dfs = (l: number, r: number, score: number): number => {
        if (r - l + 1 < 2) {
            return 0;
        }
        
        const key = `${l},${r},${score}`;
        if (memo.has(key)) {
            return memo.get(key)!;
        }
        
        let res = 0;
        
        // Try removing first two elements
        if (l + 1 <= r && nums[l] + nums[l + 1] === score) {
            res = Math.max(res, 1 + dfs(l + 2, r, score));
        }
        
        // Try removing last two elements
        if (r - 1 >= l && nums[r] + nums[r - 1] === score) {
            res = Math.max(res, 1 + dfs(l, r - 2, score));
        }
        
        // Try removing first and last elements
        if (l < r && nums[l] + nums[r] === score) {
            res = Math.max(res, 1 + dfs(l + 1, r - 1, score));
        }
        
        memo.set(key, res);
        return res;
    };
    
    let ans = 0;
    
    // Try all three possible first operations
    ans = Math.max(ans, 1 + dfs(2, n - 1, nums[0] + nums[1]));           // Remove first two
    ans = Math.max(ans, 1 + dfs(0, n - 3, nums[n - 1] + nums[n - 2]));   // Remove last two
    ans = Math.max(ans, 1 + dfs(1, n - 2, nums[0] + nums[n - 1]));       // Remove first and last
    
    return ans;
}

Complexity

  • ⏰ Time complexity: O(n^3), where n is the length of nums, due to all possible splits and memoization.
  • 🧺 Space complexity: O(n^3), for the memoization table.