Skip to content

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

  • Time: $O(n \cdot \Sigma\texttt{nums[i]} \cdot \texttt{limit} \cdot 3)$
  • Space: $O(n \cdot \Sigma\texttt{nums[i]} \cdot \texttt{limit} \cdot 3)$
 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
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;
  }
};

 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
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;
  }
}

 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
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