Maximum Product of Subsequences With an Alternating Sum Equal to K
HardPrompt
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
- Alternating Sum:
[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
- Alternating Sum:
[3, 3]- Alternating Sum:
3 - 3 = 0 - Product:
3 * 3 = 9
- Alternating Sum:
[2, 2, 3, 3]- Alternating Sum:
2 - 2 + 3 - 3 = 0 - Product:
2 * 2 * 3 * 3 = 36
- Alternating Sum:
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 <= 1500 <= nums[i] <= 12-105 <= k <= 1051 <= 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
maxProductto -1. - Create a recursive function
findMaxProduct(index, currentSubsequence). - Base Case: When
indexreaches the end of thenumsarray:- If
currentSubsequenceis not empty, calculate its alternating sum and product. - If the sum equals
kand the product is withinlimit, updatemaxProduct = max(maxProduct, product). - Return.
- If
- Recursive Step:
- Make a recursive call to
findMaxProduct(index + 1, currentSubsequence)to explore subsequences withoutnums[index]. - Add
nums[index]tocurrentSubsequence. - Make another recursive call to
findMaxProduct(index + 1, currentSubsequence)to explore subsequences withnums[index]. - Backtrack by removing
nums[index]fromcurrentSubsequence.
- Make a recursive call to
- 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.
import java.util.ArrayList;import java.util.List; class Solution { long maxProduct = -1; int k; long limit; public long maximumProduct(int[] nums, int k, int limit) { this.k = k; this.limit = limit; findMaxProduct(0, new ArrayList<>(), nums); return maxProduct; } private void findMaxProduct(int index, List<Integer> currentSubsequence, int[] nums) { if (index == nums.length) { if (!currentSubsequence.isEmpty()) { long altSum = 0; long product = 1; for (int i = 0; i < currentSubsequence.size(); i++) { if (i % 2 == 0) { altSum += currentSubsequence.get(i); } else { altSum -= currentSubsequence.get(i); } // Early exit if product exceeds limit if (currentSubsequence.get(i) == 0) { product = 0; } else if (product > 0) { // Avoid overflow if product is already large if (limit / product < currentSubsequence.get(i)) { product = limit + 1; } else { product *= currentSubsequence.get(i); } } } if (altSum == k && product <= limit) { maxProduct = Math.max(maxProduct, product); } } return; } // Exclude nums[index] findMaxProduct(index + 1, currentSubsequence, nums); // Include nums[index] currentSubsequence.add(nums[index]); findMaxProduct(index + 1, currentSubsequence, nums); currentSubsequence.remove(currentSubsequence.size() - 1); // Backtrack }}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.
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.