Maximum Product of Subsequences With an Alternating Sum Equal to K
HardUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
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 <= 1500 <= nums[i] <= 12-10^5 <= k <= 10^51 <= limit <= 5000
Solution
Method 1 – Dynamic Programming with State Compression
Intuition
We want to select a subsequence whose alternating sum is exactly k and whose product is maximized but does not exceed limit. Since the alternating sum depends on the parity of the subsequence's length, and the product constraint is tight, we use dynamic programming to track possible alternating sums and products for each parity.
Approach
- Use a DP dictionary:
dp[parity][alt_sum] = max_productwhereparityis 0 (even length) or 1 (odd length). - Initialize with an empty state:
dp[0][0] = 1(product 1 for sum 0, even length). - For each number in
nums, for each state indp, try to add the number to the subsequence:- If current parity is
p, next parity is1-p. - If next parity is odd, add the number to the alternating sum; if even, subtract it.
- Multiply the product, but only keep it if it does not exceed
limit. - Update the DP for the new state if the product is better.
- If current parity is
- After processing all numbers, the answer is the maximum product for
dp[parity][k](for any parity), but only if the product is ≤limitand the subsequence is non-empty. - If no such subsequence exists, return -1.
Code
C++
class Solution {
public:
int maximumProduct(vector<int>& nums, int k, int limit) {
unordered_map<int, unordered_map<int, int>> dp[2];
dp[0][0][1] = 1;
for (int x : nums) {
auto old = dp;
for (int p = 0; p < 2; ++p) {
for (auto& [s, m] : old[p]) {
for (auto& [prod, _] : m) {
int np = 1 - p;
int ns = (np ? s + x : s - x);
long long nprod = 1LL * prod * x;
if (nprod > limit) continue;
dp[np][ns][nprod] = max(dp[np][ns][nprod], (int)nprod);
}
}
}
}
int ans = -1;
for (int p = 0; p < 2; ++p) {
for (auto& [prod, _] : dp[p][k]) {
if (prod <= limit) ans = max(ans, prod);
}
}
return ans;
}
};
Go
func maximumProduct(nums []int, k int, limit int) int {
dp := [2]map[int]map[int]int{{0: {1: 1}}, {}}
for _, x := range nums {
old := [2]map[int]map[int]int{{}, {}}
for p := 0; p < 2; p++ {
old[p] = make(map[int]map[int]int)
for s, m := range dp[p] {
old[p][s] = make(map[int]int)
for prod := range m {
old[p][s][prod] = m[prod]
}
}
}
for p := 0; p < 2; p++ {
for s, m := range old[p] {
for prod := range m {
np := 1 - p
ns := s
if np == 1 {
ns += x
} else {
ns -= x
}
nprod := prod * x
if nprod > limit {
continue
}
if dp[np][ns] == nil {
dp[np][ns] = make(map[int]int)
}
if dp[np][ns][nprod] < nprod {
dp[np][ns][nprod] = nprod
}
}
}
}
}
ans := -1
for p := 0; p < 2; p++ {
for prod := range dp[p][k] {
if prod <= limit && prod > ans {
ans = prod
}
}
}
return ans
}
Java
import java.util.*;
class Solution {
public int maximumProduct(int[] nums, int k, int limit) {
Map<Integer, Map<Integer, Integer>>[] dp = new Map[2];
dp[0] = new HashMap<>();
dp[1] = new HashMap<>();
dp[0].put(0, new HashMap<>());
dp[0].get(0).put(1, 1);
for (int x : nums) {
Map<Integer, Map<Integer, Integer>>[] old = new Map[2];
old[0] = new HashMap<>();
old[1] = new HashMap<>();
for (int p = 0; p < 2; ++p) {
for (var e : dp[p].entrySet()) {
int s = e.getKey();
for (var f : e.getValue().entrySet()) {
int prod = f.getKey();
int np = 1 - p;
int ns = np == 1 ? s + x : s - x;
long nprod = 1L * prod * x;
if (nprod > limit) continue;
old[np].computeIfAbsent(ns, z -> new HashMap<>());
old[np].get(ns).put((int)nprod, Math.max(old[np].get(ns).getOrDefault((int)nprod, 0), (int)nprod));
}
}
}
dp = old;
}
int ans = -1;
for (int p = 0; p < 2; ++p) {
if (dp[p].containsKey(k)) {
for (int prod : dp[p].get(k).keySet()) {
if (prod <= limit) ans = Math.max(ans, prod);
}
}
}
return ans;
}
}
Kotlin
class Solution {
fun maximumProduct(nums: IntArray, k: Int, limit: Int): Int {
val dp = Array(2) { mutableMapOf<Int, MutableMap<Int, Int>>() }
dp[0][0] = mutableMapOf(1 to 1)
for (x in nums) {
val old = Array(2) { mutableMapOf<Int, MutableMap<Int, Int>>() }
for (p in 0..1) {
for ((s, m) in dp[p]) {
for (prod in m.keys) {
val np = 1 - p
val ns = if (np == 1) s + x else s - x
val nprod = prod.toLong() * x
if (nprod > limit) continue
old[np].getOrPut(ns) { mutableMapOf() }[nprod.toInt()] = nprod.toInt().coerceAtLeast(old[np][ns]?.getOrDefault(nprod.toInt(), 0) ?: 0)
}
}
}
for (p in 0..1) dp[p] = old[p]
}
var ans = -1
for (p in 0..1) {
dp[p][k]?.keys?.forEach { prod ->
if (prod <= limit) ans = maxOf(ans, prod)
}
}
return ans
}
}
Python
class Solution:
def maximumProduct(self, nums: list[int], k: int, limit: int) -> int:
from collections import defaultdict
dp = [defaultdict(dict) for _ in range(2)]
dp[0][0][1] = 1
for x in nums:
old = [defaultdict(dict) for _ in range(2)]
for p in range(2):
for s in dp[p]:
for prod in dp[p][s]:
np = 1 - p
ns = s + x if np == 1 else s - x
nprod = prod * x
if nprod > limit:
continue
old[np][ns][nprod] = max(old[np][ns].get(nprod, 0), nprod)
dp = old
ans = -1
for p in range(2):
for prod in dp[p][k]:
if prod <= limit:
ans = max(ans, prod)
return ans
Rust
use std::collections::HashMap;
impl Solution {
pub fn maximum_product(nums: Vec<i32>, k: i32, limit: i32) -> i32 {
let mut dp = vec![HashMap::new(), HashMap::new()];
dp[0].insert((0, 1), 1);
for &x in &nums {
let mut old = vec![HashMap::new(), HashMap::new()];
for p in 0..2 {
for (&(s, prod), &_) in &dp[p] {
let np = 1 - p;
let ns = if np == 1 { s + x } else { s - x };
let nprod = prod as i64 * x as i64;
if nprod > limit as i64 { continue; }
old[np].entry((ns, nprod as i32)).or_insert(nprod as i32);
}
}
dp = old;
}
let mut ans = -1;
for p in 0..2 {
for (&(s, prod), &v) in &dp[p] {
if s == k && prod <= limit {
ans = ans.max(prod);
}
}
}
ans
}
}
TypeScript
class Solution {
maximumProduct(nums: number[], k: number, limit: number): number {
let dp: Array<Map<number, Map<number, number>>> = [new Map(), new Map()];
dp[0].set(0, new Map([[1, 1]]));
for (const x of nums) {
const old: Array<Map<number, Map<number, number>>> = [new Map(), new Map()];
for (let p = 0; p < 2; ++p) {
for (const [s, m] of dp[p]) {
for (const prod of m.keys()) {
const np = 1 - p;
const ns = np === 1 ? s + x : s - x;
const nprod = prod * x;
if (nprod > limit) continue;
if (!old[np].has(ns)) old[np].set(ns, new Map());
old[np].get(ns)!.set(nprod, Math.max(old[np].get(ns)!.get(nprod) ?? 0, nprod));
}
}
}
dp = old;
}
let ans = -1;
for (let p = 0; p < 2; ++p) {
if (dp[p].has(k)) {
for (const prod of dp[p].get(k)!.keys()) {
if (prod <= limit) ans = Math.max(ans, prod);
}
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * S * P), wherenis the length of nums,Sis the number of possible alternating sums, andPis the number of possible products (pruned by limit). - 🧺 Space complexity:
O(S * P), for the DP states.