Maximum Number of Operations With the Same Score II

Maximum Number of Operations With the Same Score II - Problem

Given an array of integers called nums, you can perform any of the following operations 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.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: First operation: remove first and last (3+5=8), array becomes [2,1,4]. Second operation: remove first and last (2+4=6≠8), or first two (2+1=3≠8), or last two (1+4=5≠8). Actually, we can remove 2+4=6 if we started with a different first operation. Let's try: remove first two (3+2=5), then remove first two again (1+4=5). Total: 2 operations with score 5.

Example 2 — Simple Case

$ Input: nums = [3,2,3]

› Output: 1

💡 Note: We can remove first and last (3+3=6), leaving [2]. Only 1 operation possible since we need at least 2 elements.

Example 3 — No Valid Operations

$ Input: nums = [1,5]

› Output: 1

💡 Note: Only one operation possible: remove first and last (1+5=6). Since there are no more elements, we get 1 operation total.

Constraints

2 ≤ nums.length ≤ 2000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements that can be removed in pairs

Operation Choices

Three ways to remove pairs: first two, last two, or first+last

Same Score Constraint

All operations must have the same sum

Key Takeaway

🎯 Key Insight: Only 3 possible target scores exist - try each one with memoized recursion

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that there are only 3 possible target scores from the first operation. We try each one recursively with memoization to avoid recalculating subproblems. Best approach is memoized recursion. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(3^n)	O(n)	Try all possible sequences of operations without memoization
Memoized Recursion	O(n²)	O(n²)	Cache results to avoid recalculating same subproblems

Brute Force Recursion — Algorithm Steps

Try removing first two elements
Try removing last two elements
Try removing first and last elements
For each choice, recursively continue with that target score

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Consider all 3 possible first operations

Recurse

For each choice, try all valid next operations

Result

Return maximum operations found across all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int helper(int* nums, int left, int right, int target) {
    if (left >= right) return 0;
    
    int maxOps = 0;
    int temp;
    
    // Try removing first two
    if (left + 1 < right && nums[left] + nums[left + 1] == target) {
        temp = 1 + helper(nums, left + 2, right, target);
        if (temp > maxOps) maxOps = temp;
    }
    
    // Try removing last two
    if (right - 1 > left && nums[right - 1] + nums[right - 2] == target) {
        temp = 1 + helper(nums, left, right - 2, target);
        if (temp > maxOps) maxOps = temp;
    }
    
    // Try removing first and last
    if (left < right - 1 && nums[left] + nums[right - 1] == target) {
        temp = 1 + helper(nums, left + 1, right - 1, target);
        if (temp > maxOps) maxOps = temp;
    }
    
    return maxOps;
}

int solution(int* nums, int n) {
    if (n < 2) return 0;
    
    int maxOperations = 0;
    int temp;
    
    // Try each possible first operation
    temp = 1 + helper(nums, 2, n, nums[0] + nums[1]);
    if (temp > maxOperations) maxOperations = temp;
    
    temp = 1 + helper(nums, 0, n - 2, nums[n-1] + nums[n-2]);
    if (temp > maxOperations) maxOperations = temp;
    
    temp = 1 + helper(nums, 1, n - 1, nums[0] + nums[n-1]);
    if (temp > maxOperations) maxOperations = temp;
    
    return maxOperations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

Each operation has 3 choices, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion call stack depth up to n operations

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler