Maximum sum of subsequence with non adjacent elements

Array Divide and Conquer Dynamic Programming Segment Tree

15.4% acceptance

Feb 24, 2026

153

You are given an array nums consisting of integers. You are also given a 2D array queries, where queries[i] = [posi, xi]. For query i, we first set nums[posi] equal to xi, then we calculate the answer to query i which is the maximum sum of a subsequence of nums where no two adjacent elements are selected. Return the sum of the answers to all queries, modulo 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_sum_subsequence(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    const NEG_INF: i64 = -1_000_000_000_000_000;
    let n = nums.len();

    // Segment tree node: [f00, f01, f10, f11]
    // f[a][b]: max non-adjacent subsequence sum for this range where
    //   a=0: left boundary element can be selected (left neighbor not selected)
    //   a=1: left boundary element CANNOT be selected (left neighbor was selected)
    //   b=0: right boundary element is NOT selected
    //   b=1: right boundary element IS selected
    // Index: a*2 + b
    type Node = [i64; 4];

    fn make_empty() -> Node {
      [0, NEG_INF, 0, NEG_INF]
    }

    fn make_leaf(v: i64) -> Node {
      // f[0][0]=0 (don't take leaf), f[0][1]=v (take leaf), f[1][0]=0 (can't take), f[1][1]=-INF (contradiction)
      [0, v, 0, NEG_INF]
    }

    fn merge(left: Node, right: Node) -> Node {
      // merged[a][b] = max(left[a][0]+right[0][b], left[a][1]+right[1][b])
      // = max(left[a*2]+right[b], left[a*2+1]+right[2+b])
      let mut res = [NEG_INF; 4];
      for a in 0..2usize {
        for b in 0..2usize {
          let v1 = left[a * 2].saturating_add(right[b]);
          let v2 = left[a * 2 + 1].saturating_add(right[2 + b]);
          res[a * 2 + b] = v1.max(v2);
        }
      }
      res
    }

    let size = n.next_power_of_two();
    let mut tree: Vec<Node> = vec![make_empty(); 2 * size];

    // Initialize leaves
    for i in 0..n {
      tree[size + i] = make_leaf(nums[i] as i64);
    }

    // Build internal nodes
    for i in (1..size).rev() {
      let left = tree[2 * i];
      let right = tree[2 * i + 1];
      tree[i] = merge(left, right);
    }

    let mut total = 0i64;

    for q in &queries {
      let pos = q[0] as usize;
      let val = q[1] as i64;

      // Point update
      let mut idx = size + pos;
      tree[idx] = make_leaf(val);
      idx >>= 1;
      while idx >= 1 {
        let left = tree[2 * idx];
        let right = tree[2 * idx + 1];
        tree[idx] = merge(left, right);
        idx >>= 1;
      }

      // Query: max non-adjacent sum = max(root[0][0], root[0][1])
      let ans = tree[1][0].max(tree[1][1]).max(0);
      total = (total + ans) % MOD;
    }

    total as i32
  }
}