3040. Maximum Number of Operations With the Same Score II


Problem Description

In this problem, we're asked to focus on an array of integers called nums. We can perform an operation on this array as long as it has at least two elements left. An operation consists of choosing and deleting any two elements from the array based on the following three possibilities:

  1. The first two elements.
  2. The last two elements.
  3. The first and the last elements.

The score for an operation is calculated by summing up the deleted elements. We need to determine the maximum number of operations we can perform where each operation yields the same score. The goal is to return this maximum number of operations that all have the same score.

To understand how to approach this problem, one must recognize the constraint that every operation must yield the same score. This significantly narrows down the possibilities and directs us towards considering only specific pairs that sum up to a uniform score.

Intuition

The solution to this problem involves memorization and depth-first search (DFS) to explore all valid operations. Given the constraint that all operations must yield the same score, the initial observation is that there are only three potential scores, based on pairs that can be taken from either the beginning or the end of the array. These scores are:

  1. The sum of the first two elements.
  2. The sum of the last two elements.
  3. The sum of the first and the last elements.

Using these scores, we use DFS to determine the maximum number of pairs that can be created with the same sum. A recursive dfs function is employed to attempt to form pairs starting from different indices of the array for each of the three scores. The arguments i and j represent the current subarray's bounds we're searching, and s represents the targeted score. The function returns the maximum number of valid operations between positions i and j.

To avoid redundant calculations, we use memorization (caching the results of previous computations). This optimization is particularly useful when overlapping subproblems occur, which is a common characteristic in this kind of recursive search.

In summary, the intuition is to exhaustively search for the maximum number of pairs that can be formed for each of the three possible scores and to use caching to optimize the process. Finally, we compare the results of these three exhaustive searches to find and return the maximum achievable number of operations with the same score.

Learn more about Memoization and Dynamic Programming patterns.

Solution Approach

The solution provided utilizes a recursive DFS (Depth-First Search) strategy, coupled with memoization to significantly reduce the complexity that would typically be associated with brute force recursive algorithms due to repeated computations.

DFS with Memoization

The core algorithm is wrapped within the dfs(i, j, s) function, where i and j represent the indices defining the current subarray of nums, and s is the constant score that all operations must match.

Here's a deep dive into the dfs function steps:

  • Base Case: If the current subarray size defined by i and j is less than 2 (j - i < 1), we cannot perform any more operations, so we return 0.

  • Recursive Step: The function attempts to delete a pair of elements from either end of the current subarray or from both ends, provided the sum of the chosen elements equals s. It explores three possibilities:

    • If nums[i] + nums[i + 1] == s, deletes these elements and proceeds recursively with dfs(i + 2, j, s).
    • If nums[i] + nums[j] == s, deletes these elements and proceeds recursively with dfs(i + 1, j - 1, s).
    • If nums[j - 1] + nums[j] == s, deletes these elements and proceeds recursively with dfs(i, j - 2, s).

Each recursive call returns the maximum number of operations starting from that subsequence with indices i and j. The function keeps track of the maximum possible operations (ans) that respect the equal score rule in each subtree, essentially performing a depth-first traversal of all the valid operation sequences.

Memoization:

To avoid recalculating the results for the same subarray, the dfs function uses the @cache decorator for memoization, which stores the result of each unique (i, j, s) state. This optimization prevents duplicate calculations, which can quickly explode in a recursive algorithm.

Main Solution Workflow:

The solution block calculates the maximum possible operations for each of the three valid scores separately. For each score, we adjust the subarray and call the dfs function:

  1. The score is the sum of the first two elements: dfs(2, n - 1, nums[0] + nums[1])
  2. The score is the sum of the last two elements: dfs(0, n - 3, nums[-1] + nums[-2])
  3. The score is the sum of the first and last elements: dfs(1, n - 2, nums[0] + nums[-1])

The algorithm returns the maximum number of operations for a single score plus one (to account for the initial operation that determined the score).

This approach avoids unnecessary computations while effectively exploring all meaningful paths, leading to an efficient solution to the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example where nums = [5, 3, 1, 2, 4, 6]. The task is to find the maximum number of operations with equal scores.

According to our problem description, we have three initial scores to consider based on the first two elements, the last two elements, and the first and last elements. These scores are:

  1. nums[0] + nums[1] = 5 + 3 = 8
  2. nums[5] + nums[4] = 6 + 4 = 10
  3. nums[0] + nums[5] = 5 + 6 = 11

Each score will lead to a different path of operations and we have to explore each through DFS.

Let's pick the first score (8) and apply our DFS approach:

  • Start with dfs(2, n - 1, nums[0] + nums[1]) which is dfs(2, 5, 8). We are looking to find pairs that sum up to 8 in the subarray nums[2:6] which is [1, 2, 4, 6].

  • For the current subarray, neither the first two 1 + 2 nor the last two 4 + 6 sum up to 8, but the first and last 1 + 6 do. We can perform one operation here bringing our subarray to [2, 4].

  • With the new subarray [2, 4], we notice that 2 + 4 equals 6, not 8. Hence, we cannot perform any further operations to match our score of 8. The dfs function would return 0 for this path because we have no more valid operations.

  • The result for the first score would then be one initial operation that determined the score, plus dfs(2, 5, 8) which returns 0. So, for a score of 8, we get 1 + 0 = 1 operation.

Applying the same steps for the second and third scores (10 and 11 respectively), we would eventually find the maximum number of operations for each score and then return the largest among them. This way, we will have recursively explored all possible operations respecting the constraint that they should all yield the same score and guaranteed to have found the maximum number of such operations.

Suppose the second starting score 10 led to the maximum of 2 operations. Then, the result for our nums array would be 2 + 1 = 3 operations including the operation that yielded the initial score of 10.

This example simplifies the DFS process but illustrates the recursive nature and decision-making involved in arriving at the solution using the described approach with memoization aiding efficiency.

Solution Implementation

1from functools import lru_cache  # Import lru_cache for memoization
2
3class Solution:
4    def maxOperations(self, nums: List[int]) -> int:
5        # Use lru_cache decorator to cache the results of the recursive calls
6        @lru_cache(maxsize=None)
7        def dfs(start: int, end: int, target_sum: int) -> int:
8            # Base case: if the subarray has less than two elements, no pair can be formed
9            if end - start < 1:
10                return 0
11            max_operations = 0
12            # If the first two elements make up the target sum, explore the subproblem excluding them
13            if nums[start] + nums[start + 1] == target_sum:
14                max_operations = max(max_operations, 1 + dfs(start + 2, end, target_sum))
15            # If the first and last elements make up the target sum, explore the subproblem excluding them
16            if nums[start] + nums[end] == target_sum:
17                max_operations = max(max_operations, 1 + dfs(start + 1, end - 1, target_sum))
18            # If the last two elements make up the target sum, explore the subproblem excluding them
19            if nums[end - 1] + nums[end] == target_sum:
20                max_operations = max(max_operations, 1 + dfs(start, end - 2, target_sum))
21            return max_operations
22
23        # Calculate the total length of the array
24        n = len(nums)
25        # Try all possible pairs that include the first and last element
26        max_ops_first_two = dfs(2, n - 1, nums[0] + nums[1])
27        max_ops_last_two = dfs(0, n - 3, nums[-1] + nums[-2])
28        max_ops_first_last = dfs(1, n - 2, nums[0] + nums[-1])
29        # One operation is already counted so we add 1 to the maximum of the three possibilities
30        return 1 + max(max_ops_first_two, max_ops_last_two, max_ops_first_last)
31
1class Solution {
2    private Integer[][] memo;
3    private int[] numbers;
4    private int targetSum;
5    private int arrayLength;
6
7    // Main function to calculate the maximum operations
8    public int maxOperations(int[] nums) {
9        // Initialize class variables with the input
10        this.numbers = nums;
11        arrayLength = nums.length;
12
13        // Calculate sub-results for different array portions and starting points
14        int resultWithFirstTwo = calculateSubResult(2, arrayLength - 1, nums[0] + nums[1]);
15        int resultWithLastTwo = calculateSubResult(0, arrayLength - 3, nums[arrayLength - 2] + nums[arrayLength - 1]);
16        int resultWithFirstAndLast = calculateSubResult(1, arrayLength - 2, nums[0] + nums[arrayLength - 1]);
17
18        // Return 1 plus the maximum of the calculated sub-results
19        return 1 + Math.max(resultWithFirstTwo, Math.max(resultWithLastTwo, resultWithFirstAndLast));
20    }
21
22    // Helper to set up and start the DFS search on sub-arrays
23    private int calculateSubResult(int i, int j, int s) {
24        memo = new Integer[arrayLength][arrayLength]; // Memoization table
25        this.targetSum = s; // The desired sum for a pair
26        return depthFirstSearch(i, j);
27    }
28
29    // Depth First Search to find the maximum operations
30    private int depthFirstSearch(int i, int j) {
31        // Base case: If there is less than 2 elements, no pairs can be formed
32        if (j - i < 1) {
33            return 0;
34        }
35
36        // If we already computed the value for this sub-array, return it
37        if (memo[i][j] != null) {
38            return memo[i][j];
39        }
40
41        int maxOperations = 0;
42
43        // If the first two elements form a pair, proceed to check the remaining elements
44        if (numbers[i] + numbers[i + 1] == targetSum) {
45            maxOperations = Math.max(maxOperations, 1 + depthFirstSearch(i + 2, j));
46        }
47
48        // If the first and last elements form a pair, proceed to check the remaining elements
49        if (numbers[i] + numbers[j] == targetSum) {
50            maxOperations = Math.max(maxOperations, 1 + depthFirstSearch(i + 1, j - 1));
51        }
52
53        // If the last two elements form a pair, proceed to check the remaining elements
54        if (numbers[j - 1] + numbers[j] == targetSum) {
55            maxOperations = Math.max(maxOperations, 1 + depthFirstSearch(i, j - 2));
56        }
57
58        // Save the result in memo table before returning
59        memo[i][j] = maxOperations;
60        return maxOperations;
61    }
62}
63
1#include <vector>
2#include <cstring>
3#include <functional>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10    int maxOperations(vector<int>& nums) {
11        // Get the size of the nums vector
12        int n = nums.size();
13      
14        // Create a memoization table
15        int dp[n][n];
16      
17        // Define a lambda function to perform DFS and compute maximum operations
18        auto computeMaxOperations = [&](int start, int end, int targetSum) -> int {
19            // Initialize dp with -1 to indicate unvisited states
20            memset(dp, -1, sizeof(dp));
21          
22            // Define the DFS function to find pairs that sum up to targetSum
23            function<int(int, int)> dfs = [&](int left, int right) -> int {
24                // If there are less than two elements, no more pairs can be formed
25                if (right - left < 1) {
26                    return 0;
27                }
28              
29                // Return already computed value to avoid recomputation
30                if (dp[left][right] != -1) {
31                    return dp[left][right];
32                }
33              
34                int maxPairs = 0; // Initialize maxPairs to 0
35              
36                // Check if the first two numbers form a valid pair and choose the maximum result
37                if (nums[left] + nums[left + 1] == targetSum) {
38                    maxPairs = max(maxPairs, 1 + dfs(left + 2, right));
39                }
40              
41                // Check if the first and last numbers form a valid pair and choose the maximum result
42                if (nums[left] + nums[right] == targetSum) {
43                    maxPairs = max(maxPairs, 1 + dfs(left + 1, right - 1));
44                }
45              
46                // Check if the last two numbers form a valid pair and choose the maximum result
47                if (nums[right - 1] + nums[right] == targetSum) {
48                    maxPairs = max(maxPairs, 1 + dfs(left, right - 2));
49                }
50              
51                // Save and return the result
52                return dp[left][right] = maxPairs;
53            };
54          
55            // Execute dfs starting from the given start and end indices
56            return dfs(start, end);
57        };
58      
59        // Using the first two numbers in nums, calculate maximum number of operations
60        int option1 = computeMaxOperations(2, n - 1, nums[0] + nums[1]);
61        // Using the last two numbers in nums, calculate maximum number of operations
62        int option2 = computeMaxOperations(0, n - 3, nums[n - 2] + nums[n - 1]);
63        // Using the first and last number in nums, calculate maximum number of operations
64        int option3 = computeMaxOperations(1, n - 2, nums[0] + nums[n - 1]);
65      
66        // Return the maximum of the three options plus one (the one used for the calculation)
67        return 1 + max({option1, option2, option3});
68    }
69};
70
1// Define a new memoization array to store the results of subproblems
2let memo: number[][];
3
4// This helper method initializes the memoization array
5function initializeMemo(n: number): void {
6    memo = Array.from({ length: n }, () => Array(n).fill(-1));
7}
8
9// This method computes the maximum number of operations by using a DFS approach
10// with memoization to avoid recomputation of subproblems
11function computeMaxOperations(i: number, j: number, targetSum: number): number {
12    // Base case: if there are less than two elements remaining, cannot form a pair
13    if (j - i < 1) {
14        return 0;
15    }
16    // If the result of the current subproblem is already computed, return it
17    if (memo[i][j] !== -1) {
18        return memo[i][j];
19    }
20    let ans = 0;
21    // Check if the two elements at the start of the range add up to the target sum
22    if (nums[i] + nums[i + 1] === targetSum) {
23        ans = Math.max(ans, 1 + computeMaxOperations(i + 2, j, targetSum));
24    }
25    // Check if the first and last elements in the range add up to the target sum
26    if (nums[i] + nums[j] === targetSum) {
27        ans = Math.max(ans, 1 + computeMaxOperations(i + 1, j - 1, targetSum));
28    }
29    // Check if the two elements at the end of the range add up to the target sum
30    if (nums[j - 1] + nums[j] === targetSum) {
31        ans = Math.max(ans, 1 + computeMaxOperations(i, j - 2, targetSum));
32    }
33    // Memoize and return the maximum number of operations that can be performed
34    memo[i][j] = ans;
35    return ans;
36}
37
38function maxOperations(nums: number[]): number {
39    const n = nums.length;
40    // Initialize the memo array with proper length and filled with -1
41    initializeMemo(n);
42    // Calculate the maximum operations for each of the three possible starting pairs
43    const resultA = computeMaxOperations(2, n - 1, nums[0] + nums[1]);
44    const resultB = computeMaxOperations(0, n - 3, nums[n - 2] + nums[n - 1]);
45    const resultC = computeMaxOperations(1, n - 2, nums[0] + nums[n - 1]);
46    // Return the maximum of the three calculations incremented by one
47    // because we're starting with one operation already made
48    return 1 + Math.max(resultA, resultB, resultC);
49}
50

Time and Space Complexity

The time complexity of the given code is O(n^2) where n is the length of the input list nums. This is because the dfs function that is used to compute the answer is called recursively, and at each step, it considers either incrementing the left pointer by 2, incrementing the left pointer and decrementing the right pointer, or decrementing the right pointer by 2. Therefore, at most n/2 recursive calls can be made at each level of recursion before base cases are reached, and there are n possible positions for the left and right pointers, which results in O(n^2) recursive calls in the worst case.

The space complexity of the code is also O(n^2) due to the memoization (@cache) used in the recursive dfs function. This memoization stores results for each unique pair of indices (i, j) to avoid redundant calculations. Since there can be n choices for i and n choices for j, there can be at most O(n^2) unique states to store, which determines the space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More