Maximum sum of alternating subsequence with distance at least k

31.2% acceptance

May 13, 2026

You are given an integer array nums of length n and an integer k. Pick a subsequence with indices 0 <= i1 < i2 < ... < im < n such that: For every 1 <= t < m, it+1 - it >= k. The selected values form a strictly alternating sequence. In other words, either: nums[i1] < nums[i2] > nums[i3] < ..., or nums[i1] > nums[i2] < nums[i3] > ... A subsequence of length 1 is also considered strictly alternating. The score of a valid subsequence is the sum of its selected values. Return an integer denoting the maximum possible score of a valid subsequence.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_alternating_sum(nums: Vec<i32>, k: i32) -> i64 {
    const NEG_INF: i64 = i64::MIN / 4;
    fn update(bit: &mut [i64], mut i: usize, v: i64) {
      while i < bit.len() {
        if v > bit[i] { bit[i] = v; }
        i += i & i.wrapping_neg();
      }
    }
    fn query(bit: &[i64], mut i: usize) -> i64 {
      let mut res = NEG_INF;
      while i > 0 {
        if bit[i] > res { res = bit[i]; }
        i &= i - 1;
      }
      res
    }
    let n = nums.len();
    let k = k as usize;
    let max_v: usize = *nums.iter().max().unwrap() as usize;
    let v_size = max_v + 2;
    let mut bit_a = vec![NEG_INF; v_size + 1];
    let mut bit_b = vec![NEG_INF; v_size + 1];
    let mut a = vec![NEG_INF; n];
    let mut b = vec![NEG_INF; n];
    let mut ans: i64 = nums.iter().map(|&x| x as i64).max().unwrap();
    for i in 0..n {
      if i >= k {
        let j = i - k;
        let v = nums[j] as usize;
        update(&mut bit_a, v, a[j]);
        update(&mut bit_b, v_size + 1 - v, b[j]);
      }
      let v = nums[i] as i64;
      let pref_a = if nums[i] >= 1 {
        query(&bit_a, (nums[i] - 1) as usize)
      } else { NEG_INF };
      let suf_b = query(&bit_b, v_size - nums[i] as usize);
      let f_hi = if pref_a > NEG_INF / 2 { pref_a + v } else { NEG_INF };
      let f_lo = if suf_b > NEG_INF / 2 { suf_b + v } else { NEG_INF };
      a[i] = f_lo.max(v);
      b[i] = f_hi.max(v);
      if f_hi > ans { ans = f_hi; }
      if f_lo > ans { ans = f_lo; }
    }
    ans
  }
}