Maximum Product of Subsequences With an Alternating Sum Equal to K

Hard

#3121Time: O(2^n * n). There are 2^n possible subsequences. For each, we iterate through its elements to calculate the alternating sum and product, which takes O(n) time in the worst case.Space: O(n), where n is the length of `nums`. This is for the recursion stack depth and to store the `currentSubsequence`.

Patterns

Dynamic Programming

Data structures

Array Hash Table

Prompt

You are given an integer array nums and two integers, k and limit. Your task is to find a non-empty subsequence of nums that:

Has an alternating sum equal to k.
Maximizes the product of all its numbers without the product exceeding limit.

Return the product of the numbers in such a subsequence. If no subsequence satisfies the requirements, return -1.

The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.

Example 1:

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

Output: 6

Explanation:

The subsequences with an alternating sum of 2 are:

[1, 2, 3]
- Alternating Sum: 1 - 2 + 3 = 2
- Product: 1 * 2 * 3 = 6
[2]
- Alternating Sum: 2
- Product: 2

The maximum product within the limit is 6.

Example 2:

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

Output: -1

Explanation:

A subsequence with an alternating sum of exactly -5 does not exist.

Example 3:

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

Output: 9

Explanation:

The subsequences with an alternating sum of 0 are:

[2, 2]
- Alternating Sum: 2 - 2 = 0
- Product: 2 * 2 = 4
[3, 3]
- Alternating Sum: 3 - 3 = 0
- Product: 3 * 3 = 9
[2, 2, 3, 3]
- Alternating Sum: 2 - 2 + 3 - 3 = 0
- Product: 2 * 2 * 3 * 3 = 36

The subsequence [2, 2, 3, 3] has the greatest product with an alternating sum equal to k, but 36 > 9. The next greatest product is 9, which is within the limit.

Constraints:

1 <= nums.length <= 150
0 <= nums[i] <= 12
-10⁵ <= k <= 10⁵
1 <= limit <= 5000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach explores all possible non-empty subsequences of the nums array. For each subsequence, it calculates the alternating sum and the product of its elements. If the alternating sum equals k and the product does not exceed limit, it compares this product with the maximum product found so far and updates it if necessary.

Algorithm

Initialize a global variable maxProduct to -1.
Create a recursive function findMaxProduct(index, currentSubsequence).
Base Case: When index reaches the end of the nums array:
- If currentSubsequence is not empty, calculate its alternating sum and product.
- If the sum equals k and the product is within limit, update maxProduct = max(maxProduct, product).
- Return.
Recursive Step:
- Make a recursive call to findMaxProduct(index + 1, currentSubsequence) to explore subsequences without nums[index].
- Add nums[index] to currentSubsequence.
- Make another recursive call to findMaxProduct(index + 1, currentSubsequence) to explore subsequences with nums[index].
- Backtrack by removing nums[index] from currentSubsequence.
Start the process by calling findMaxProduct(0, new ArrayList<>()).
Return the final maxProduct.

Walkthrough

We can implement this using a recursive helper function, say findMaxProduct(index, currentSubsequence). The index parameter tracks the current element in nums to consider, and currentSubsequence is a list storing the elements of the subsequence being built. The recursion has two branches at each step: one for excluding the current element nums[index] and one for including it. The base case for the recursion is when index reaches the end of the nums array. At this point, if the currentSubsequence is not empty, we compute its properties and update a global maximum product if the conditions are met.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    long maxProduct = -1;6    int k;7    long limit;8 9    public long maximumProduct(int[] nums, int k, int limit) {10        this.k = k;11        this.limit = limit;12        findMaxProduct(0, new ArrayList<>(), nums);13        return maxProduct;14    }15 16    private void findMaxProduct(int index, List<Integer> currentSubsequence, int[] nums) {17        if (index == nums.length) {18            if (!currentSubsequence.isEmpty()) {19                long altSum = 0;20                long product = 1;21                for (int i = 0; i < currentSubsequence.size(); i++) {22                    if (i % 2 == 0) {23                        altSum += currentSubsequence.get(i);24                    } else {25                        altSum -= currentSubsequence.get(i);26                    }27                    // Early exit if product exceeds limit28                    if (currentSubsequence.get(i) == 0) {29                        product = 0;30                    } else if (product > 0) { // Avoid overflow if product is already large31                         if (limit / product < currentSubsequence.get(i)) {32                            product = limit + 1;33                         } else {34                            product *= currentSubsequence.get(i);35                         }36                    }37                }38 39                if (altSum == k && product <= limit) {40                    maxProduct = Math.max(maxProduct, product);41                }42            }43            return;44        }45 46        // Exclude nums[index]47        findMaxProduct(index + 1, currentSubsequence, nums);48 49        // Include nums[index]50        currentSubsequence.add(nums[index]);51        findMaxProduct(index + 1, currentSubsequence, nums);52        currentSubsequence.remove(currentSubsequence.size() - 1); // Backtrack53    }54}

Complexity

Time

O(2^n * n). There are 2^n possible subsequences. For each, we iterate through its elements to calculate the alternating sum and product, which takes O(n) time in the worst case.

Space

O(n), where n is the length of `nums`. This is for the recursion stack depth and to store the `currentSubsequence`.

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to find the correct answer if it runs to completion.

Cons

Extremely inefficient due to its exponential time complexity.
Will time out for the given constraints on nums.length.

This approach uses dynamic programming to efficiently solve the problem. We iterate through the numbers in the input array and build up solutions for subsequences. The state of our DP table tracks the maximum product for subsequences characterized by their alternating sum and length parity (even or odd). The length parity is essential as it determines whether a new element contributes positively or negatively to the alternating sum. By only keeping track of parity instead of the full length, we significantly reduce the state space.

Algorithm

First, calculate the maximum possible absolute value of an alternating sum, let's call it S_max. If abs(k) > S_max, no solution is possible, so return -1.
Create a 2D DP table, dp[2][2 * S_max + 1], and initialize all its values to -1. dp[p][s] will store the maximum product for a subsequence with length parity p and alternating sum s.
Use an offset (S_max) to map the sum s (which can be negative) to a non-negative array index s + S_max.
Initialize dp[0][S_max] = 1 to represent the base case: an empty subsequence has an even length (0), a sum of 0, and a product of 1.
Iterate through each num in the nums array:
- Create a temporary new_dp table as a copy of the current dp table.
- Iterate through each state (p, s) in the dp table that has been reached (i.e., dp[p][s + S_max] != -1).
- For each such state, calculate the new state that results from appending num to the subsequence. The new parity is 1-p, the new sum is s + num (if p=0) or s - num (if p=1), and the new product is dp[p][s + S_max] * num.
- If the new product does not exceed limit, update the corresponding entry in new_dp: new_dp[new_p][new_s + S_max] = max(new_dp[new_p][new_s + S_max], new_product).
- After checking all states, replace dp with new_dp.
After iterating through all numbers, the answer is max(dp[0][k + S_max], dp[1][k + S_max]).

Walkthrough

We define a 2D DP table, dp[parity][sum], where dp[parity][sum] stores the maximum product of a subsequence with length parity parity (0 for even, 1 for odd) and an alternating sum of sum. The range of possible sums is determined by the array size and element values. With n <= 150 and nums[i] <= 12, the sum is bounded. We calculate the maximum possible sum S_max and use an offset to handle negative sums with array indices.

We initialize dp[0][offset_for_0] = 1 for an empty subsequence (length 0, sum 0, product 1). Then, for each number num in nums, we compute a new DP table based on the previous one. For each existing state (p, s) with product prod, we consider including num. This creates a new subsequence with length parity 1-p, a new sum, and a new product prod * num. If this new product is within the limit, we update the corresponding entry in the new DP table. After processing all numbers, the final DP table holds the maximum products for all reachable (parity, sum) combinations.

1import java.util.Arrays;2 3class Solution {4    public long maximumProduct(int[] nums, int k, int limit) {5        int n = nums.length;6        int maxVal = 0;7        for (int num : nums) {8            maxVal = Math.max(maxVal, num);9        }10 11        // Maximum possible alternating sum magnitude12        int maxSum = (n + 1) / 2 * maxVal;13 14        if (Math.abs(k) > maxSum) {15            return -1;16        }17 18        int offset = maxSum;19        int sumRange = 2 * maxSum + 1;20 21        long[][] dp = new long[2][sumRange];22        for (long[] row : dp) {23            Arrays.fill(row, -1);24        }25        dp[0][offset] = 1; // {parity, sum_with_offset} -> max_product26 27        for (int num : nums) {28            long[][] newDp = new long[2][sumRange];29            for (int i = 0; i < 2; i++) {30                System.arraycopy(dp[i], 0, newDp[i], 0, sumRange);31            }32 33            for (int p = 0; p < 2; p++) {34                for (int s_offset = 0; s_offset < sumRange; s_offset++) {35                    if (dp[p][s_offset] != -1) {36                        long currentProduct = dp[p][s_offset];37                        int s = s_offset - offset;38                        39                        // Case: Append num to the subsequence40                        int newP = 1 - p;41                        int newS = (p == 0) ? s + num : s - num;42                        43                        if (Math.abs(newS) <= maxSum) {44                            long newProduct = currentProduct * num;45                            if (newProduct <= limit) {46                                int newS_offset = newS + offset;47                                newDp[newP][newS_offset] = Math.max(newDp[newP][newS_offset], newProduct);48                            }49                        }50                    }51                }52            }53            dp = newDp;54        }55 56        long result = Math.max(dp[0][k + offset], dp[1][k + offset]);57        return result;58    }59}

Complexity

Time

O(n * S), where `n` is the length of `nums` and `S` is the range of possible alternating sums. `S` is proportional to `n * max_val`. Thus, the total time complexity is `O(n^2 * max_val)`.

Space

O(n * max_val). The space is dominated by the DP table, which has a size of `2 * (2 * S_max + 1)`. Since `S_max` is `O(n * max_val)`, the space complexity is `O(n * max_val)`.

Trade-offs

Pros

Highly efficient and capable of solving the problem within the given constraints.
Systematically builds the solution, avoiding re-computation of subproblems.

Cons

More complex to conceptualize and implement compared to brute force.
Requires careful handling of DP states, transitions, and array indexing with offsets.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem