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.

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

1
2
3
4

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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^5 <= k <= 10^5
  • 1 <= limit <= 5000

Examples

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

  1. Use a DP dictionary: dp[parity][alt_sum] = max_product where parity is 0 (even length) or 1 (odd length).
  2. Initialize with an empty state: dp[0][0] = 1 (product 1 for sum 0, even length).
  3. For each number in nums, for each state in dp, try to add the number to the subsequence:
    • If current parity is p, next parity is 1-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.
  4. After processing all numbers, the answer is the maximum product for dp[parity][k] (for any parity), but only if the product is ≤ limit and the subsequence is non-empty.
  5. If no such subsequence exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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), where n is the length of nums, S is the number of possible alternating sums, and P is the number of possible products (pruned by limit).
  • 🧺 Space complexity: O(S * P), for the DP states.