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 Product of Subsequences With an Alternating Sum Equal to K

Number: 3777

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums and two integers k and limit, select a non-empty subsequence of nums such that:

  • The alternating sum of the subsequence equals k. (The alternating sum is computed by adding the 0th, 2nd, 4th, … elements and subtracting the 1st, 3rd, 5th, … elements of the subsequence.)
  • The product of the elements in the subsequence is as large as possible, but does not exceed the given limit. If no such subsequence exists, return -1; otherwise, return the product of the chosen subsequence.

Key Insights

  • When forming a subsequence the “parity” of the index (even or odd) determines whether a number is added or subtracted.
  • We can build a state that tracks three things: the current product (which must remain <= limit), the current alternating sum, and the parity (whether the next number will be added or subtracted).
  • A dynamic programming solution is useful. We iterate over the array and for each number decide either to skip it or to append it to any existing subsequence; when appending the number, update:
    • New product = old product * current number (ensuring it is within limit).
    • New alternating sum = old sum + current number if the current subsequence length is even, or old sum – current number if odd.
    • Flip the parity for the next appended number.
  • We maintain states in two buckets (parity 0 and parity 1). The “empty” state is used to start new subsequences but must be excluded in the final answer.
  • Because limit is small (up to 5000) and each element is at most 12, we can use dp where the product dimension ranges from 0 to limit.

Space and Time Complexity

Time Complexity: O(n * P * S) in the worst case where n is the length of nums, P is the number of distinct product values (bounded by limit) and S is the number of alternating sum states for each product. In practice the limit (5000) and relatively small multiplication factors (≤12) keep the state space manageable. Space Complexity: O(P * S), as we store reachable states in dictionaries keyed by product for both parity groups.

Solution

We use dynamic programming by maintaining two dictionaries corresponding to the two possible parities – whether the current subsequence length is even (parity 0) or odd (parity 1). Each dictionary maps a product value (obtained so far) to a set of achievable alternating sums. • Initially, we start with an “empty” state (parity 0 with product 1 and alternating sum 0) that serves as a seed for starting new subsequences. • For each number in nums, two choices exist:

  • Skip the number (keep old states).
  • Append the number to an existing subsequence: • If the current state has parity 0 (even length), then the number to be appended is placed at an even index so we add its value. The new state becomes of parity 1. • If the current state has parity 1 (odd length), then the number is subtracted (since it occupies an odd index). The new state becomes parity 0. • The product is updated by multiplication and must remain ≤ limit. • In addition, each new number can start a new subsequence on its own. • Finally, iterate over all stored states (from both parity groups) while ignoring the “empty” seed. For each state having an alternating sum equal to k, we select the maximum product. • If no valid subsequence is found, return -1.

Code Solutions

# Python solution with line-by-line comments

def maxProductSubsequence(nums, k, limit):
    # dp[parity] is a dictionary:
    # key: product computed so far, value: set of possible alternating sums for sequences with that product and current parity.
    # Parity 0 indicates that the next appended number will be added, 
    # while parity 1 indicates that the next number will be subtracted.
    
    from collections import defaultdict
    # Initialize dp with the empty subsequence (length 0, parity 0).
    dp = [defaultdict(set), defaultdict(set)]
    dp[0][1].add(0)  # empty subsequence: product=1 and alternating sum=0, but note: this is a seed.
    
    for num in nums:
        # Prepare new states for this iteration as copies of the current states (skipping the number)
        new_dp = [defaultdict(set), defaultdict(set)]
        # Copy over existing states
        for parity in (0, 1):
            for prod, sums in dp[parity].items():
                for s in sums:
                    new_dp[parity][prod].add(s)
        
        # Start a new subsequence with the current number
        # For a new subsequence, there is no “previous state” except starting fresh,
        # so the first element is at index 0 which is even so we add the number.
        if num <= limit:
            new_dp[1][num].add(num)  # parity becomes 1 after adding one element
        
        # Try to append the current number to each existing subsequence
        for parity in (0, 1):
            for prod, sums in dp[parity].items():
                for alt_sum in sums:
                    new_prod = prod * num
                    # Only update if product remains within limit and avoid multiplying the seed 1 if no real element chosen
                    if new_prod <= limit:
                        if parity == 0:
                            # current subsequence length is even, so next index is even -> add the number
                            new_parity = 1
                            new_alt_sum = alt_sum + num
                        else:
                            # current subsequence length is odd, so next index is odd -> subtract the number
                            new_parity = 0
                            new_alt_sum = alt_sum - num
                        new_dp[new_parity][new_prod].add(new_alt_sum)
        # Update dp with new states for next iteration
        dp = new_dp

    # Now, search for any subsequence (ignore the empty state which is product 1 and alt_sum 0 in dp[0])
    answer = -1
    for parity in (0, 1):
        for prod, sums in dp[parity].items():
            # Exclude the initial empty seed state (product==1 and alternating sum==0)
            if prod == 1 and 0 in sums:
                # Check if there are other valid sums if any; empty subsequence is not allowed.
                if len(sums) == 1:
                    continue
            if k in sums:
                answer = max(answer, prod)
    return answer

# Example usage:
print(maxProductSubsequence([1,2,3], 2, 10))  # Expected output: 6
print(maxProductSubsequence([0,2,3], -5, 12)) # Expected output: -1
print(maxProductSubsequence([2,2,3,3], 0, 9))  # Expected output: 9
← Back to All Questions