3509. Maximum Product of Subsequences With an Alternating Sum Equal to K LeetCode Solution

Last updated: April 9, 2025

In this guide, you will get 3509. Maximum Product of Subsequences With an Alternating Sum Equal to K LeetCode Solution with the best time and space complexity. The solution to Maximum Product of Subsequences With an Alternating Sum Equal to K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Maximum Product of Subsequences With an Alternating Sum Equal to K solution in C++
  4. Maximum Product of Subsequences With an Alternating Sum Equal to K solution in Java
  5. Maximum Product of Subsequences With an Alternating Sum Equal to K solution in Python
  6. Additional Resources
3509. Maximum Product of Subsequences With an Alternating Sum Equal to K LeetCode Solution image

Problem Statement of Maximum Product of Subsequences With an Alternating Sum Equal to K

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

Complexity Analysis

  • Time Complexity: O(n \cdot \Sigma\texttt{nums[i]} \cdot \texttt{limit} \cdot 3)
  • Space Complexity: O(n \cdot \Sigma\texttt{nums[i]} \cdot \texttt{limit} \cdot 3)

3509. Maximum Product of Subsequences With an Alternating Sum Equal to K LeetCode Solution in C++

enum class State {
  kFirst,     // first element - add to sum and start product
  kSubtract,  // second element - subtract from sum and multiply product
  kAdd        // third element - add to sum and multiply product
};

class Solution {
 public:
  int maxProduct(vector<int>& nums, int k, int limit) {
    if (abs(k) > accumulate(nums.begin(), nums.end(), 0))
      return -1;
    unordered_map<string, int> mem;
    const int ans = maxProduct(nums, 0, 1, State::kFirst, k, limit, mem);
    return ans == kMin ? -1 : ans;
  }

 private:
  static constexpr int kMin = -5000;

  int maxProduct(const vector<int>& nums, int i, int product, State state,
                 int k, int limit, unordered_map<string, int>& mem) {
    if (i == nums.size())
      return k == 0 && state != State::kFirst && product <= limit ? product
                                                                  : kMin;
    const string key = to_string(i) + "," + to_string(k) + "," +
                       to_string(product) + "," +
                       to_string(static_cast<int>(state));
    if (mem.contains(key))
      return mem[key];
    int res = maxProduct(nums, i + 1, product, state, k, limit, mem);
    if (state == State::kFirst)
      res = max(res, maxProduct(nums, i + 1, nums[i], State::kSubtract,
                                k - nums[i], limit, mem));
    if (state == State::kSubtract)
      res = max(res, maxProduct(nums, i + 1, min(product * nums[i], limit + 1),
                                State::kAdd, k + nums[i], limit, mem));
    if (state == State::kAdd)
      res = max(res, maxProduct(nums, i + 1, min(product * nums[i], limit + 1),
                                State::kSubtract, k - nums[i], limit, mem));
    return mem[key] = res;
  }
};
/* code provided by PROGIEZ */

3509. Maximum Product of Subsequences With an Alternating Sum Equal to K LeetCode Solution in Java

enum State {
  FIRST,    // first element - add to sum and start product
  SUBTRACT, // second element - subtract from sum and multiply product
  ADD       // third element - add to sum and multiply product
}

class Solution {
  public int maxProduct(int[] nums, int k, int limit) {
    if (Math.abs(k) > Arrays.stream(nums).sum())
      return -1;
    final Map<String, Integer> mem = new HashMap<>();
    final int ans = maxProduct(nums, 0, 1, State.FIRST, k, limit, mem);
    return ans == MIN ? -1 : ans;
  }

  private static final int MIN = -5000;

  private int maxProduct(int[] nums, int i, int product, State state, int k, int limit,
                         Map<String, Integer> mem) {
    if (i == nums.length)
      return k == 0 && state != State.FIRST && product <= limit ? product : MIN;
    final String key = i + "," + k + "," + product + "," + state.ordinal();
    if (mem.containsKey(key))
      return mem.get(key);
    int res = maxProduct(nums, i + 1, product, state, k, limit, mem);
    if (state == State.FIRST)
      res =
          Math.max(res, maxProduct(nums, i + 1, nums[i], State.SUBTRACT, k - nums[i], limit, mem));
    if (state == State.SUBTRACT)
      res = Math.max(res, maxProduct(nums, i + 1, Math.min(product * nums[i], limit + 1), State.ADD,
                                     k + nums[i], limit, mem));
    if (state == State.ADD)
      res = Math.max(res, maxProduct(nums, i + 1, Math.min(product * nums[i], limit + 1),
                                     State.SUBTRACT, k - nums[i], limit, mem));
    mem.put(key, res);
    return res;
  }
}
// code provided by PROGIEZ

3509. Maximum Product of Subsequences With an Alternating Sum Equal to K LeetCode Solution in Python

from enum import Enum


class State(Enum):
  FIRST = 0  # first element - add to sum and start product
  SUBTRACT = 1  # second element - subtract from sum and multiply product
  ADD = 2  # third element - add to sum and multiply product


class Solution:
  def maxProduct(self, nums: list[int], k: int, limit: int) -> int:
    MIN = -5000
    if abs(k) > sum(nums):
      return -1

    @functools.lru_cache(None)
    def dp(i: int, product: int, state: State, k: int) -> int:
      if i == len(nums):
        return (product if k == 0 and state != State.FIRST and product <= limit
                else MIN)
      res = dp(i + 1, product, state, k)
      if state == State.FIRST:
        res = max(res, dp(i + 1, nums[i], State.SUBTRACT, k - nums[i]))
      if state == State.SUBTRACT:
        res = max(res, dp(i + 1, min(product * nums[i], limit + 1),
                          State.ADD, k + nums[i]))
      if state == State.ADD:
        res = max(res, dp(i + 1, min(product * nums[i], limit + 1),
                          State.SUBTRACT, k - nums[i]))
      return res

    ans = dp(0, 1, State.FIRST, k)
    return -1 if ans == MIN else ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.