# Maximum Product of Subsequences With an Alternating Sum Equal to K
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-product-of-subsequences-with-an-alternating-sum-equal-to-k)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-subsequences-with-an-alternating-sum-equal-to-k
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table
---
## 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:**

**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`
* `-105 <= k <= 105`
* `1 <= limit <= 5000`

# Approaches
## Brute-Force Recursion
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.
**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`.
**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`.
### Explanation
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.

```java
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
    }
}
```
### 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`.

## Dynamic Programming with State Compression
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.
**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)`.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public long maximumProduct(int[] nums, int k, int limit) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        // Maximum possible alternating sum magnitude
        int maxSum = (n + 1) / 2 * maxVal;

        if (Math.abs(k) > maxSum) {
            return -1;
        }

        int offset = maxSum;
        int sumRange = 2 * maxSum + 1;

        long[][] dp = new long[2][sumRange];
        for (long[] row : dp) {
            Arrays.fill(row, -1);
        }
        dp[0][offset] = 1; // {parity, sum_with_offset} -> max_product

        for (int num : nums) {
            long[][] newDp = new long[2][sumRange];
            for (int i = 0; i < 2; i++) {
                System.arraycopy(dp[i], 0, newDp[i], 0, sumRange);
            }

            for (int p = 0; p < 2; p++) {
                for (int s_offset = 0; s_offset < sumRange; s_offset++) {
                    if (dp[p][s_offset] != -1) {
                        long currentProduct = dp[p][s_offset];
                        int s = s_offset - offset;
                        
                        // Case: Append num to the subsequence
                        int newP = 1 - p;
                        int newS = (p == 0) ? s + num : s - num;
                        
                        if (Math.abs(newS) <= maxSum) {
                            long newProduct = currentProduct * num;
                            if (newProduct <= limit) {
                                int newS_offset = newS + offset;
                                newDp[newP][newS_offset] = Math.max(newDp[newP][newS_offset], newProduct);
                            }
                        }
                    }
                }
            }
            dp = newDp;
        }

        long result = Math.max(dp[0][k + offset], dp[1][k + offset]);
        return result;
    }
}
```
### 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])`.