Maximum Number of Operations With the Same Score II

Medium
1492.

Maximum Number of Operations With the Same Score II

Maximum Number of Operations With the Same Score II is a medium coding problem on arrays, dynamic programming and memoization, asked in Amazon and Google interviews.

While nums has at least two elements you may perform an operation of one of three kinds:

  • delete the first two elements,
  • delete the last two elements, or
  • delete the first and the last element.

The score of an operation is the sum of the two deleted elements. Perform as many operations as possible such that all of them have the same score, and return that maximum number of operations.

Example 1

Input
nums = [3,2,1,2,3,4]
Output
3
Explanation
Delete 3 and 2 (score 5), then 1 and 4 (first and last), then 2 and 3.

Example 2

Input
nums = [3,2,6,1,4]
Output
2
Explanation
Delete 3 and 2 (score 5), then the last two, 1 and 4 (score 5). Only `[6]` is left.

Example 3

Input
nums = [7,7]
Output
1

Constraints

  • 2 <= nums.length <= 2000
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxOperations = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Operations With the Same Score II Solution

Maximum Number of Operations With the Same Score II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Number of Operations With the Same Score II is a medium coding problem on arrays, dynamic programming and memoization, asked in Amazon and Google interviews.

Problem statement

While nums has at least two elements you may perform an operation of one of three kinds:

  • delete the first two elements,
  • delete the last two elements, or
  • delete the first and the last element.

The score of an operation is the sum of the two deleted elements. Perform as many operations as possible such that all of them have the same score, and return that maximum number of operations.

Example 1

Input: nums = [3,2,1,2,3,4]
Output: 3
Explanation: Delete 3 and 2 (score 5), then 1 and 4 (first and last), then 2 and 3.

Example 2

Input: nums = [3,2,6,1,4]
Output: 2
Explanation: Delete 3 and 2 (score 5), then the last two, 1 and 4 (score 5). Only `[6]` is left.

Example 3

Input: nums = [7,7]
Output: 1

Constraints

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

Hints for Maximum Number of Operations With the Same Score II

  1. Hint 1

    The first operation fixes the score, and it can only be one of three sums: nums[0] + nums[1], nums[n-2] + nums[n-1] or nums[0] + nums[n-1].

  2. Hint 2

    After any sequence of operations the remaining elements form a contiguous window nums[l..r].

  3. Hint 3

    For each of the three scores, run an interval DP over windows: f(l, r) = most operations on nums[l..r], trying each of the three deletions that match the score.

How to solve Maximum Number of Operations With the Same Score II

Every operation removes from the ends, so the state is the window [l, r] that remains. Fix the score (three candidates) and memoise the best number of operations per window.

Approach

  1. For each candidate score S in {nums[0]+nums[1], nums[n-2]+nums[n-1], nums[0]+nums[n-1]}:
  2. Define f(l, r) = 0 when fewer than two elements remain; otherwise the maximum of 1 + f(l+2, r) if nums[l]+nums[l+1] = S, 1 + f(l, r-2) if nums[r-1]+nums[r] = S, and 1 + f(l+1, r-1) if nums[l]+nums[r] = S.
  3. Fill the table bottom-up by increasing window length (or memoise top-down).
  4. Return the largest f(0, n-1) over the three scores.

Why it works

The first operation must be one of the three listed deletions, so the common score is one of three values; for a fixed score, every legal continuation from window [l, r] is one of the three moves, and each leads to a smaller window solved optimally by the DP.

Complexity

  • Time — O(n²)
  • Space — O(n²)

Pitfalls

  • Trying every possible score instead of the three candidates multiplies the work for nothing.
  • The window shrinks by two each time — windows of length 0 and 1 are the base cases.
  • A greedy that always deletes the first matching pair can miss longer sequences.

Reference solution

Python

from typing import List

def maxOperations(nums: List[int]) -> int:
    n = len(nums)

    def solve(score):
        # h[l][r] = most operations on the window nums[l:r]
        h = [[0] * (n + 1) for _ in range(n + 1)]
        for length in range(2, n + 1):
            for l in range(n - length + 1):
                r = l + length
                best = 0
                if nums[l] + nums[l + 1] == score:
                    best = 1 + h[l + 2][r]
                if nums[r - 2] + nums[r - 1] == score and 1 + h[l][r - 2] > best:
                    best = 1 + h[l][r - 2]
                if nums[l] + nums[r - 1] == score and 1 + h[l + 1][r - 1] > best:
                    best = 1 + h[l + 1][r - 1]
                h[l][r] = best
        return h[0][n]

    return max(solve(nums[0] + nums[1]), solve(nums[-2] + nums[-1]), solve(nums[0] + nums[-1]))

Java

static int sameScoreSolve(int[] nums, int score) {
    int n = nums.length;
    int[][] h = new int[n + 1][n + 1];
    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len <= n; l++) {
            int r = l + len;
            int best = 0;
            if (nums[l] + nums[l + 1] == score) best = 1 + h[l + 2][r];
            if (nums[r - 2] + nums[r - 1] == score) best = Math.max(best, 1 + h[l][r - 2]);
            if (nums[l] + nums[r - 1] == score) best = Math.max(best, 1 + h[l + 1][r - 1]);
            h[l][r] = best;
        }
    }
    return h[0][n];
}

public static int maxOperations(int[] nums) {
    int n = nums.length;
    int a = sameScoreSolve(nums, nums[0] + nums[1]);
    int b = sameScoreSolve(nums, nums[n - 2] + nums[n - 1]);
    int c = sameScoreSolve(nums, nums[0] + nums[n - 1]);
    return Math.max(a, Math.max(b, c));
}

C++

int sameScoreSolve(const vector<int>& nums, int score) {
    int n = nums.size();
    vector<vector<int>> h(n + 1, vector<int>(n + 1, 0));
    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len <= n; l++) {
            int r = l + len;
            int best = 0;
            if (nums[l] + nums[l + 1] == score) best = 1 + h[l + 2][r];
            if (nums[r - 2] + nums[r - 1] == score) best = max(best, 1 + h[l][r - 2]);
            if (nums[l] + nums[r - 1] == score) best = max(best, 1 + h[l + 1][r - 1]);
            h[l][r] = best;
        }
    }
    return h[0][n];
}

int maxOperations(vector<int>& nums) {
    int n = nums.size();
    int a = sameScoreSolve(nums, nums[0] + nums[1]);
    int b = sameScoreSolve(nums, nums[n - 2] + nums[n - 1]);
    int c = sameScoreSolve(nums, nums[0] + nums[n - 1]);
    return max(a, max(b, c));
}

JavaScript

var maxOperations = function(nums) {
    var n = nums.length;
    var solve = function(score) {
        var h = [];
        for (var i = 0; i <= n; i++) h.push(new Array(n + 1).fill(0));
        for (var len = 2; len <= n; len++) {
            for (var l = 0; l + len <= n; l++) {
                var r = l + len;
                var best = 0;
                if (nums[l] + nums[l + 1] === score) best = 1 + h[l + 2][r];
                if (nums[r - 2] + nums[r - 1] === score && 1 + h[l][r - 2] > best) best = 1 + h[l][r - 2];
                if (nums[l] + nums[r - 1] === score && 1 + h[l + 1][r - 1] > best) best = 1 + h[l + 1][r - 1];
                h[l][r] = best;
            }
        }
        return h[0][n];
    };
    return Math.max(solve(nums[0] + nums[1]), solve(nums[n - 2] + nums[n - 1]), solve(nums[0] + nums[n - 1]));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming