Maximum product of subsequences with an alternating sum equal to k

Array Hash Table Dynamic Programming

13.0% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_product(nums: Vec<i32>, k: i32, limit: i32) -> i32 {
    use std::collections::{HashMap, HashSet};

    const MAX_ALT: i32 = 1800; // max |alt_sum| for n=150, nums[i]<=12
    if k.abs() > MAX_ALT {
      return -1;
    }

    // dp[(parity, alt_sum)] = (products, over_limit_reachable)
    //   products: set of achievable products <= limit for this state
    //   over_limit_reachable: reachable with some product (possibly > limit),
    //     used so that a future v=0 can collapse any reachable state to product=0.
    // parity 0: next element is at even index (added)
    // parity 1: next element is at odd index (subtracted)
    //
    // Tracking reachability separately handles the case where v=0:
    // a state reachable with product > limit can still yield product 0 when
    // extended by 0, which is always <= limit.
    //
    // We store ALL achievable products (not just the max) because when extending
    // with a large v, a lower product p might satisfy p*v <= limit even though
    // max_valid*v > limit. All nums[i] are in [0,12] so products are 12-smooth
    // numbers bounded by limit (<=5000), keeping each set small in practice.
    type State = (HashSet<i32>, bool);
    let mut dp: HashMap<(i8, i32), State> = HashMap::new();

    for &v in &nums {
      let mut adds: HashMap<(i8, i32), State> = HashMap::new();

      // Start a new subsequence with v placed at even index (position 0)
      {
        let e = adds.entry((1i8, v)).or_insert_with(|| (HashSet::new(), false));
        e.1 = true; // reachable
        if v <= limit {
          e.0.insert(v);
        }
      }

      // Extend existing states by appending v
      for (&(par, alt), (prods, over)) in dp.iter() {
        if !over && prods.is_empty() {
          continue;
        }
        let sign = if par == 0 { 1i32 } else { -1 };
        let new_alt = alt + sign * v;
        if new_alt.abs() > MAX_ALT {
          continue;
        }
        let new_par = 1 - par;
        let e = adds.entry((new_par, new_alt)).or_insert_with(|| (HashSet::new(), false));
        // new state is reachable if old state was reachable at all
        e.1 |= *over || !prods.is_empty();
        if v == 0 {
          // Any reachable predecessor gives product 0, always valid
          if *over || !prods.is_empty() {
            e.0.insert(0);
          }
        } else {
          for &p in prods.iter() {
            let np = p * v;
            if np <= limit {
              e.0.insert(np);
            }
          }
        }
      }

      // Merge adds into dp
      for (key, (new_prods, new_over)) in adds {
        let e = dp.entry(key).or_insert_with(|| (HashSet::new(), false));
        e.1 |= new_over;
        for p in new_prods {
          e.0.insert(p);
        }
      }
    }

    let mut best = -1i32;
    for par in [0i8, 1i8] {
      if let Some((prods, _)) = dp.get(&(par, k)) {
        if let Some(&m) = prods.iter().max() {
          best = best.max(m);
        }
      }
    }

    best
  }
}