We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Operations With the Same Score II

Number: 3318

Difficulty: Medium

Paid? No

Companies: Microsoft, Apple

Problem Description

Given an integer array nums, you are allowed to repeatedly perform an operation while nums has at least 2 elements. In each operation you may choose one of the following choices to remove two numbers from the current (contiguous) array: • Remove the first two elements. • Remove the last two elements. • Remove the first and the last elements. The score of an operation is defined as the sum of the two deleted elements. Your task is to obtain the maximum number of operations you can perform so that all operations have the same score.

Key Insights

  • Because removals always occur at the ends, after each operation the remaining array is contiguous.
  • Any valid sequence of removals induces a partition of the array into pairs, where each pair is either a “left‐pair” (first two elements), a “right‐pair” (last two elements), or an “outer pair” (first and last element).
  • All pairs must have the same sum S. Thus, it makes sense to “fix” a candidate target S and then check the maximum number of valid operations possible.
  • For each fixed S candidate (which comes from sums of array elements), one can use a dynamic programming approach over subarrays (tracked by indices l and r) which represents the maximum operations possible from that subarray under the constraint that every chosen pair has sum S.

Space and Time Complexity

Time Complexity: O(U * n²), where n is the length of nums and U is the number of candidate sums (typically derived from pairs in the array).
Space Complexity: O(n²) for the DP table (per candidate S).

Solution

We solve the problem by “fixing” a target sum S and then using DP over intervals. Define dp(l, r) as the maximum number of valid operations we can perform on the subarray nums[l…r] if we require every pair removal to have score S. The valid transitions are: • If the first two elements sum to S (i.e. nums[l] + nums[l+1] == S), then one operation is performed and we continue with dp(l+2, r).
• If the outer two elements sum to S (nums[l] + nums[r] == S), then one operation is executed and we move to dp(l+1, r-1).
• If the last two elements sum to S (nums[r-1] + nums[r] == S), then one operation is done and we proceed with dp(l, r-2).
We compute dp(0, n-1) for every candidate S (only considering those values that actually appear as a pair sum in nums) and take the maximum result.

Key details include ensuring that the subarray has at least 2 elements before attempting an operation and handling the boundaries correctly. This DP naturally reflects the fact that the removal always happens at the ends of the current array, keeping it contiguous.

Code Solutions

# Python Code Solution with line-by-line comments
def maxOperationsWithSameScore(nums):
    n = len(nums)
    # Collect candidate target sums from possible pairs in the array.
    candidate_sums = set()
    for i in range(n):
        for j in range(i+1, n):
            candidate_sums.add(nums[i] + nums[j])
    
    # Function to compute maximum operations using DP for a fixed target sum S.
    def compute_for_S(S):
        # dp[l][r] will hold the max operations possible on nums[l...r]
        dp = [[0]*(n) for _ in range(n)]
        # Consider subarrays of increasing length
        for length in range(2, n+1):
            for l in range(0, n-length+1):
                r = l + length - 1
                best = 0
                # Option 1: Remove first two elements if they sum to S.
                if l+1 <= r and nums[l] + nums[l+1] == S:
                    best = max(best, 1 + (dp[l+2][r] if l+2 <= r else 0))
                # Option 2: Remove outer pair if they sum to S.
                if nums[l] + nums[r] == S:
                    best = max(best, 1 + (dp[l+1][r-1] if l+1 <= r-1 else 0))
                # Option 3: Remove last two elements if they sum to S.
                if r-1 >= l and nums[r-1] + nums[r] == S:
                    best = max(best, 1 + (dp[l][r-2] if l <= r-2 else 0))
                dp[l][r] = best
        return dp[0][n-1]
    
    max_ops = 0
    # Try each candidate sum S.
    for S in candidate_sums:
        max_ops = max(max_ops, compute_for_S(S))
        
    return max_ops

# Example usage:
print(maxOperationsWithSameScore([3,2,1,2,3,4]))  # Expected output 3
print(maxOperationsWithSameScore([3,2,6,1,4]))    # Expected output 2
← Back to All Questions