Problem

You are given an array of integers nums. Consider the following operation:

  • Delete the first two elements nums and define the score of the operation as the sum of these two elements.

You can perform this operation until nums contains fewer than two elements. Additionally, the same score must be achieved in all operations.

Return the maximum number of operations you can perform.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: nums = [3,2,1,4,5]

Output: 2

Explanation:

  * We can perform the first operation with the score `3 + 2 = 5`. After this operation, `nums = [1,4,5]`.
  * We can perform the second operation as its score is `4 + 1 = 5`, the same as the previous operation. After this operation, `nums = [5]`.
  * As there are fewer than two elements, we can't perform more operations.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: nums = [1,5,3,3,4,1,3,2,2,3]

Output: 2

Explanation:

  * We can perform the first operation with the score `1 + 5 = 6`. After this operation, `nums = [3,3,4,1,3,2,2,3]`.
  * We can perform the second operation as its score is `3 + 3 = 6`, the same as the previous operation. After this operation, `nums = [4,1,3,2,2,3]`.
  * We cannot perform the next operation as its score is `4 + 1 = 5`, which is different from the previous scores.

Example 3

1
2
3
4


Input: nums = [5,3]

Output: 1

Constraints

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

Solution

Method 1 – Prefix Sum Simulation

Intuition

The score for each operation is the sum of the first two elements. To maximize the number of operations, try all possible initial scores (from the first two elements), and simulate the process for each, counting how many times you can keep removing pairs with the same score.

Approach

  1. For each possible initial score (sum of the first two elements), simulate the process:
    • Remove the first two elements and check if their sum equals the score.
    • Continue as long as the sum matches and at least two elements remain.
  2. Track the maximum number of operations found for any possible initial score.
  3. Return the maximum number of operations.

Code

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

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int i = 1; i < n; ++i) {
            int score = nums[0] + nums[i];
            int cnt = 0, l = 0, r = i;
            while (r + 1 < n) {
                if (nums[l] + nums[r] == score) {
                    cnt++;
                    l = r + 1;
                    r = l + 1;
                } else {
                    break;
                }
            }
            ans = max(ans, cnt + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maxOperations(nums []int) int {
    n, ans := len(nums), 0
    for i := 1; i < n; i++ {
        score := nums[0] + nums[i]
        cnt, l, r := 0, 0, i
        for r+1 < n {
            if nums[l]+nums[r] == score {
                cnt++
                l = r + 1
                r = l + 1
            } else {
                break
            }
        }
        if cnt+1 > ans {
            ans = cnt + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxOperations(int[] nums) {
        int n = nums.length, ans = 0;
        for (int i = 1; i < n; i++) {
            int score = nums[0] + nums[i];
            int cnt = 0, l = 0, r = i;
            while (r + 1 < n) {
                if (nums[l] + nums[r] == score) {
                    cnt++;
                    l = r + 1;
                    r = l + 1;
                } else {
                    break;
                }
            }
            ans = Math.max(ans, cnt + 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

class Solution {
    fun maxOperations(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        for (i in 1 until n) {
            val score = nums[0] + nums[i]
            var cnt = 0
            var l = 0
            var r = i
            while (r + 1 < n) {
                if (nums[l] + nums[r] == score) {
                    cnt++
                    l = r + 1
                    r = l + 1
                } else {
                    break
                }
            }
            ans = maxOf(ans, cnt + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxOperations(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(1, n):
            score = nums[0] + nums[i]
            cnt, l, r = 0, 0, i
            while r + 1 < n:
                if nums[l] + nums[r] == score:
                    cnt += 1
                    l = r + 1
                    r = l + 1
                else:
                    break
            ans = max(ans, cnt + 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

impl Solution {
    pub fn max_operations(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for i in 1..n {
            let score = nums[0] + nums[i];
            let mut cnt = 0;
            let mut l = 0;
            let mut r = i;
            while r + 1 < n {
                if nums[l] + nums[r] == score {
                    cnt += 1;
                    l = r + 1;
                    r = l + 1;
                } else {
                    break;
                }
            }
            ans = ans.max(cnt + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    maxOperations(nums: number[]): number {
        const n = nums.length;
        let ans = 0;
        for (let i = 1; i < n; i++) {
            const score = nums[0] + nums[i];
            let cnt = 0, l = 0, r = i;
            while (r + 1 < n) {
                if (nums[l] + nums[r] === score) {
                    cnt++;
                    l = r + 1;
                    r = l + 1;
                } else {
                    break;
                }
            }
            ans = Math.max(ans, cnt + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), since for each possible initial score, we may scan the array.
  • 🧺 Space complexity: O(1), as we use only a few variables.