Maximize Score After Pair Deletions - Practice Coding Problems

Maximize Score After Pair Deletions - Problem

Array Greedy Medium

You are given an array of integers nums. You must repeatedly perform one of the following operations while the array has more than two elements:

Remove the first two elements.
Remove the last two elements.
Remove the first and last element.

For each operation, add the sum of the removed elements to your total score.

Return the maximum possible score you can achieve.

Input & Output

Example 1 — Basic Case

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

› Output: 15

💡 Note: Multiple ways to achieve score 15: Remove [6,2] (score 8), then [3,4] (score 7). Total: 8+7=15. Or remove [3,4] first (score 7), then [6,2] (score 8). Both give maximum score 15.

Example 2 — Small Array

$ Input: nums = [2,7,9,4,5]

› Output: 27

💡 Note: Optimal sequence: Remove [2,5] (first+last, score 7), then [7,4] (first+last, score 11), leaving [9] (score 9). Total: 7+11+9=27.

Example 3 — Minimum Size

$ Input: nums = [1,2]

› Output: 3

💡 Note: Array has exactly 2 elements, so we sum them all: 1+2=3. No operations are performed since we need more than 2 elements to operate.

Constraints

2 ≤ nums.length ≤ 10³
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [6,2,3,4] with 3 possible operations

Strategy Choice

Each operation removes 2 elements and adds their sum to score

Maximum Score

Find the sequence of operations that maximizes total score

Key Takeaway

🎯 Key Insight: Use dynamic programming to explore all possible operation sequences and find the maximum score efficiently

Asked in

G Google 15 f Facebook 12 a Amazon 8

This problem requires finding the maximum score by strategically removing pairs of elements. The key insight is that at each step, we have exactly 3 choices and need to pick the one leading to maximum total score. The optimal approach uses dynamic programming to solve overlapping subproblems efficiently. Time: O(n²), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n²)	O(n²)	Cache results of subproblems to avoid redundant calculations
Bottom-Up Dynamic Programming	O(n³)	O(n²)	Build solution iteratively using 2D table for all subarray ranges
Brute Force Recursion	O(3ⁿ)	O(n)	Try all possible sequences of operations recursively

Memoization (Top-Down DP) — Algorithm Steps

Step 1: Use recursion with left/right pointers
Step 2: Check cache before calculating
Step 3: Try all 3 operations and take maximum
Step 4: Store result in cache before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate solve(0,3) for [6,2,3,4]

Cache Results

Store results of all subproblems

Reuse Cache

Return cached values for repeated calls

Code -

solution.c — C

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

struct MemoEntry {
    int left, right, value;
};

struct MemoEntry memo[1000];
int memoSize = 0;
int nums[100];

int max(int a, int b) {
    return a > b ? a : b;
}

int getMemo(int left, int right) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].left == left && memo[i].right == right) {
            return memo[i].value;
        }
    }
    return -1;
}

void setMemo(int left, int right, int value) {
    memo[memoSize].left = left;
    memo[memoSize].right = right;
    memo[memoSize].value = value;
    memoSize++;
}

int solve(int left, int right) {
    int cached = getMemo(left, right);
    if (cached != -1) {
        return cached;
    }
    
    if (right - left + 1 <= 2) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        setMemo(left, right, sum);
        return sum;
    }
    
    // Option 1: Remove first two
    int option1 = nums[left] + nums[left + 1] + solve(left + 2, right);
    
    // Option 2: Remove last two
    int option2 = nums[right - 1] + nums[right] + solve(left, right - 2);
    
    // Option 3: Remove first and last
    int option3 = nums[left] + nums[right] + solve(left + 1, right - 1);
    
    int result = max(option1, max(option2, option3));
    setMemo(left, right, result);
    return result;
}

int solution(int* arr, int size) {
    memoSize = 0;
    for (int i = 0; i < size; i++) {
        nums[i] = arr[i];
    }
    return solve(0, size - 1);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(arr, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each unique (left,right) pair computed once, there are O(n²) such pairs

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores results for all subarray ranges plus recursion stack

⚠ Quadratic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

750 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

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler