LeetCode 3509 - Maximum Product of Subsequences With an Alternating Sum Equal to K

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Dynamic Programming

Solution

Problem Understanding

The problem asks us to find a subsequence of a given integer array nums such that the alternating sum of the subsequence equals a target integer k, while maximizing the product of the numbers in that subsequence without exceeding a given limit. The alternating sum is defined as the sum of elements at even indices minus the sum of elements at odd indices, for the selected subsequence. The subsequence can be any selection of elements in order from nums, and it must be non-empty.

The input nums is an array of integers ranging from 0 to 12, with length up to 150. The value of k can be negative, zero, or positive. The limit restricts the maximum allowable product, which means even if a subsequence achieves the correct alternating sum, it might be disqualified if its product exceeds the limit.

The expected output is a single integer: the maximum product of all valid subsequences whose alternating sum equals k and whose product does not exceed limit. If no subsequence meets both criteria, we return -1.

Important edge cases include:

Arrays with only zeros or ones, which can lead to alternating sums of zero or products equal to 1.
k outside the possible alternating sum range, which guarantees -1.
Subsequence products exceeding the limit, which requires careful handling to avoid overflow.
Arrays with repeated elements that can form multiple valid subsequences.

Approaches

A brute-force approach would be to generate all possible subsequences of nums, calculate the alternating sum for each, and keep track of the maximum product that satisfies the constraints. This is correct in principle but exponentially slow because the number of subsequences of an array of length n is $2^n - 1$, which is infeasible for n up to 150.

The key insight for an optimal solution is to use dynamic programming. We can maintain a DP table that tracks possible alternating sums at each index, and for each sum, the maximum product achievable without exceeding the limit. Since numbers are small (0-12), the product can be stored safely within the given limit, and the sum range is bounded by n * 12, which is feasible. We also need to account for alternating signs depending on whether the next element is treated as an "even" or "odd" index in the subsequence.

By maintaining a map or table of dp[alternating_sum] = max_product, we can iteratively consider including or skipping each element, updating potential sums and products efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generate all subsequences, compute alternating sum and product, infeasible for n = 150
Optimal (DP)	O(n * sum_range * log(limit))	O(sum_range)	DP using a hash map to track max product for each alternating sum; sum_range is the possible alternating sum range

Algorithm Walkthrough

Initialize a dynamic programming dictionary dp to store the maximum product for a given alternating sum. Start with dp = {0: 1}, representing an empty subsequence with alternating sum 0 and product 1 (we handle the empty case separately when returning the answer).
Iterate through each number num in nums. For each num, create a temporary dictionary new_dp to store updates.
For each key-value pair (sum_val, prod_val) in dp, consider two possibilities:

Include num as the next element at an even index in the subsequence, updating the alternating sum as sum_val + num and product as prod_val * num.
Include num as the next element at an odd index, updating the alternating sum as sum_val - num and product similarly.

Only update new_dp if the resulting product does not exceed limit. For each alternating sum, store the maximum product encountered.
Merge new_dp back into dp, taking the maximum product for each sum key.
After processing all numbers, if k exists in dp, return dp[k]. Otherwise, return -1.

Why it works: The DP table ensures we consider all valid subsequences while pruning suboptimal products. At each step, we maintain the best achievable product for every possible alternating sum, guaranteeing correctness. The problem asks us to find a non-empty subsequence of a given integer array nums such that its alternating sum equals a target value k and the product of its elements is maximized without exceeding a given limit. The alternating sum is calculated by taking elements at even indices, summing them, and subtracting the sum of elements at odd indices.

A subsequence is a sequence derived from the array by deleting zero or more elements without changing the order of the remaining elements. For example, for nums = [1, 2, 3], [1, 3] is a valid subsequence, but [2, 1] is not.

The input constraints provide key information about the problem scale. The array length is up to 150, each number ranges from 0 to 12, the alternating sum k can be large negative or positive, and the product limit is up to 5000. This indicates that naive approaches generating all subsequences will be too slow, as the number of subsequences grows exponentially with the array size.

Edge cases to consider include arrays where no subsequence can achieve k, subsequences that exceed limit even if their alternating sum is correct, and subsequences consisting of zeros, which do not contribute to the alternating sum but may influence the product.

Approaches

The brute-force approach would be to generate all possible subsequences of nums, compute their alternating sums, and track the maximum product that does not exceed limit for subsequences where the alternating sum equals k. This is correct in principle because it examines every possibility, but the number of subsequences for an array of length n is 2^n, which is infeasible for n up to 150.

The key insight for an optimal solution is that the problem can be treated as a dynamic programming problem over subsequences. We can track, for each index, a mapping from alternating sum differences to the maximum product achievable without exceeding limit. Since numbers are small (0 to 12) and limit is also small (up to 5000), this makes it feasible to maintain the products in the DP table while pruning values exceeding limit. At each step, we have the choice to include the current number as either part of an even-indexed or odd-indexed position in the subsequence, or skip it entirely. By updating the DP state carefully, we can efficiently explore all valid subsequences without generating them explicitly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Enumerate all subsequences, calculate alternating sum and product
Optimal	O(n * k_range * log(limit))	O(k_range * log(limit))	Dynamic programming with hash maps for alternating sum to product mappings

Algorithm Walkthrough

Initialize a DP dictionary, where the key is the alternating sum difference and the value is a set of achievable products not exceeding limit. Start with {0: {1}} to represent an empty subsequence with alternating sum 0 and product 1.
Iterate through each number in nums. For each number, consider two possibilities: adding it as the next even index or as the next odd index in the subsequence. For each existing sum in the DP table, update the new sum and product accordingly, only including products that do not exceed limit.
Use a temporary DP dictionary for each number to avoid overwriting states prematurely.
Merge the temporary DP back into the main DP dictionary after processing each number, ensuring that for each alternating sum, only the maximum products under the limit are retained.
After processing all numbers, check if the target alternating sum k exists in the DP dictionary. If it does, return the maximum product for that sum. If not, return -1.

Why it works: The algorithm maintains a dynamic state of all possible alternating sums and corresponding maximum products at each step. By considering each number in both even and odd positions, it guarantees that all valid subsequences are accounted for, and pruning by limit ensures efficiency.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxProduct(self, nums: List[int], k: int, limit: int) -> int:
        dp = {0: 1}  # alternating sum -> max product
        
        for num in nums:
            new_dp = dp.copy()
            for sum_val, prod_val in dp.items():
                # Treat num as next even index
                new_sum = sum_val + num
                new_prod = prod_val * num
                if new_prod <= limit:
                    new_dp[new_sum] = max(new_dp.get(new_sum, 0), new_prod)
                
                # Treat num as next odd index
                new_sum = sum_val - num
                if num != 0:  # avoid multiplying by zero again
                    new_prod = prod_val * num
                if new_prod <= limit:
                    new_dp[new_sum] = max(new_dp.get(new_sum, 0), new_prod)
            dp = new_dp
        
        return dp.get(k, -1)

Explanation: We maintain a dictionary mapping alternating sums to the maximum product achievable. For each number, we consider adding it as either an even or odd index, updating the sums and products, and only keeping products within the limit. After processing all numbers, dp[k] gives the maximum product, or -1 if not achievable. dp = defaultdict(set) dp[0].add(1)

    for num in nums:
        temp = defaultdict(set)
        for alt_sum, products in dp.items():
            for prod in products:
                # Add num at even position
                new_sum_even = alt_sum + num
                new_prod_even = prod * num
                if new_prod_even <= limit:
                    temp[new_sum_even].add(new_prod_even)
                
                # Add num at odd position
                new_sum_odd = alt_sum - num
                new_prod_odd = prod * num
                if new_prod_odd <= limit:
                    temp[new_sum_odd].add(new_prod_odd)
                
                # Keep original
                temp[alt_sum].add(prod)
        
        dp = temp
    
    if k not in dp:
        return -1
    return max(dp[k])


The Python implementation uses a `defaultdict` of sets to track all achievable products for each alternating sum. For each number, it explores the three possibilities: add as even, add as odd, or skip. It ensures that only products below the limit are kept, preventing unnecessary growth in state size. Finally, it retrieves the maximum product corresponding to the target alternating sum `k`.

## Go Solution

```go
func maxProduct(nums []int, k int, limit int) int {
    dp := map[int]int{0: 1} // alternating sum -> max product
    
    for _, num := range nums {
        newDp := make(map[int]int)
        for sumVal, prodVal := range dp {
            // Copy existing entry
            if existing, ok := newDp[sumVal]; !ok || existing < prodVal {
                newDp[sumVal] = prodVal
            }
            
            // Even index
            newSum := sumVal + num
            newProd := prodVal * num
            if newProd <= limit {
                if existing, ok := newDp[newSum]; !ok || existing < newProd {
                    newDp[newSum] = newProd
                }
            }
            
            // Odd index
            newSum = sumVal - num
            if num != 0 {
                newProd = prodVal * num
            }
            if newProd <= limit {
                if existing, ok := newDp[newSum]; !ok || existing < newProd {
                    newDp[newSum] = newProd
                }
            }
        }
        dp = newDp
    }
    
    if val, ok := dp[k]; ok {
        return val
package main

func maxProduct(nums []int, k int, limit int) int {
    dp := map[int]map[int]struct{}{0: {1: {}}}
    
    for _, num := range nums {
        temp := map[int]map[int]struct{}{}
        for altSum, products := range dp {
            for prod := range products {
                // Add num at even position
                newSumEven := altSum + num
                newProdEven := prod * num
                if newProdEven <= limit {
                    if temp[newSumEven] == nil {
                        temp[newSumEven] = map[int]struct{}{}
                    }
                    temp[newSumEven][newProdEven] = struct{}{}
                }
                // Add num at odd position
                newSumOdd := altSum - num
                newProdOdd := prod * num
                if newProdOdd <= limit {
                    if temp[newSumOdd] == nil {
                        temp[newSumOdd] = map[int]struct{}{}
                    }
                    temp[newSumOdd][newProdOdd] = struct{}{}
                }
                // Keep original
                if temp[altSum] == nil {
                    temp[altSum] = map[int]struct{}{}
                }
                temp[altSum][prod] = struct{}{}
            }
        }
        dp = temp
    }
    
    if products, ok := dp[k]; ok {
        maxProd := -1
        for prod := range products {
            if prod > maxProd {
                maxProd = prod
            }
        }
        return maxProd
    }
    return -1
}

Go Notes: We use a map[int]int for DP, similar to Python. Maps are copied for updates. Edge cases such as zero multiplication are handled. Go lacks default dictionary behavior, so we check existence before comparison.

Worked Examples

Example 1: nums = [1,2,3], k = 2, limit = 10

Initial dp = {0:1}

Processing 1:

Even: sum 1, product 1
Odd: sum -1, product 1

dp = {0:1, 1:1, -1:1}

Processing 2:

For sum 0: Even: 2, product 2; Odd: -2, product 2
For sum 1: Even: 3, product 2; Odd: -1, product 2
For sum -1: Even: 1, product 2; Odd: -3, product 2

dp = {0:1, 1:2, -1:2, 2:2, -2:2, 3:2, -3:2}

Processing 3:

Updates result in dp[2] = 6 (subsequence [1,2,3])

Return 6.

Example 2: nums = [0,2,3], k = -5, limit = 12

After processing all numbers, dp has no -5 key → return -1.

Example 3: nums = [2,2,3,3], k = 0, limit = 9

Best product within limit is 9 (subsequence [3,3]). In Go, we use a map[int]map[int]struct{} to simulate a set of products for each alternating sum. The logic mirrors the Python version, iterating through numbers and updating the DP state. Go requires explicit creation of nested maps to simulate sets.

Worked Examples

Example 1: nums = [1, 2, 3], k = 2, limit = 10

Step	DP State (alt_sum: products)
Start	{0: {1}}
num=1	{0: {1}, 1: {1}, -1: {1}}
num=2	{0: {1,2}, 1: {1,2}, -1: {1,2}, 3: {2}, -3: {2}}
num=3	include/exclude → final {2: {6, 2}}
Result	max(dp[2]) = 6

Example 2: nums = [0,2,3], k=-5, limit=12

No subsequence reaches -5, so output is -1.

Example 3: nums = [2,2,3,3], k=0, limit=9

Maximum product ≤ limit for alternating sum 0 is 9.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * sum_range)	We iterate through n elements, updating possible alternating sums, where sum_range is at most n_12_2 for positive and negative sums.
Space	O(sum_range)	DP dictionary stores at most one value per possible alternating sum.

The algorithm leverages small numbers and product limit to keep DP state tractable, avoiding exponential blowup.

Test Cases

# Provided examples
assert Solution().maxProduct([1,2,3
assert Solution().maxProduct([1,2,3], 2, 10) == 6  # multiple subsequences with alt sum 2
assert Solution().maxProduct([0,2,3], -5, 12) == -1  # no valid subsequence
assert Solution().maxProduct([2,2,3,3], 0, 9) == 9  # largest valid product under limit

# Edge cases
assert Solution().maxProduct([0,0,0], 0, 5) == 0  # subsequence with zeros
assert Solution().maxProduct([12]*