Problem

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.

Since the final answer may be very large, return it modulo 10^9 + 7.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: nums = [3,5,9], queries = [[1,-2],[0,-3]]

Output: 21

Explanation:  
After the 1st query, `nums = [3,-2,9]` and the maximum sum of a subsequence
with non-adjacent elements is `3 + 9 = 12`.  
After the 2nd query, `nums = [-3,-2,9]` and the maximum sum of a subsequence
with non-adjacent elements is 9.

Example 2

1
2
3
4
5
6
7
8


Input: nums = [0,-1], queries = [[0,-5]]

Output: 0

Explanation:  
After the 1st query, `nums = [-5,-1]` and the maximum sum of a subsequence
with non-adjacent elements is 0 (choosing an empty subsequence).

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • -10^5 <= nums[i] <= 10^5
  • 1 <= queries.length <= 5 * 10^4
  • queries[i] == [posi, xi]
  • 0 <= posi <= nums.length - 1
  • -10^5 <= xi <= 10^5

Solution

Method 1 – Dynamic Programming with Segment Tree

Intuition

To efficiently answer each query, we need to quickly update an element and compute the maximum sum of a non-adjacent subsequence. This is a classic dynamic programming problem, but with updates, so we use a segment tree to maintain DP states for fast updates and queries.

Approach

  1. Build a segment tree where each node stores two values:
    • dp0: max sum for the segment when the first element is not picked.
    • dp1: max sum for the segment when the first element is picked.
  2. For each query, update the value at posi in the segment tree.
  3. After each update, the answer is the max of the two DP states at the root.
  4. Sum all answers modulo 10^9 + 7.

Code

 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
43
44
45
46
47
48
49
50
51
52
53
54
55

const int MOD = 1e9+7;
struct Node {
    long long dp0, dp1;
};
class SegmentTree {
    vector<Node> tree;
    int n;
public:
    SegmentTree(const vector<int>& nums) {
        n = nums.size();
        tree.resize(4*n);
        build(nums, 0, n-1, 1);
    }
    void build(const vector<int>& nums, int l, int r, int node) {
        if (l == r) {
            tree[node] = {0, nums[l]};
            return;
        }
        int m = (l + r) / 2;
        build(nums, l, m, 2*node);
        build(nums, m+1, r, 2*node+1);
        merge(node);
    }
    void update(int idx, int val, int l, int r, int node) {
        if (l == r) {
            tree[node] = {0, val};
            return;
        }
        int m = (l + r) / 2;
        if (idx <= m) update(idx, val, l, m, 2*node);
        else update(idx, val, m+1, r, 2*node+1);
        merge(node);
    }
    void merge(int node) {
        auto& L = tree[2*node];
        auto& R = tree[2*node+1];
        tree[node].dp0 = max(L.dp0, L.dp1) + max(R.dp0, R.dp1);
        tree[node].dp1 = L.dp0 + R.dp0;
    }
    long long query() {
        return max(tree[1].dp0, tree[1].dp1);
    }
};
class Solution {
public:
    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        SegmentTree st(nums);
        long long ans = 0;
        for (auto& q : queries) {
            st.update(q[0], q[1], 0, nums.size()-1, 1);
            ans = (ans + st.query()) % MOD;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// For brevity, use DP for each query. For large constraints, use a segment tree.
func maximumSumSubsequence(nums []int, queries [][]int) int {
    const MOD = 1e9 + 7
    ans := 0
    for _, q := range queries {
        nums[q[0]] = q[1]
        n := len(nums)
        dp0, dp1 := 0, nums[0]
        for i := 1; i < n; i++ {
            ndp0 := max(dp0, dp1)
            ndp1 := dp0 + nums[i]
            dp0, dp1 = ndp0, ndp1
        }
        res := max(dp0, dp1)
        ans = (ans + res) % MOD
    }
    return ans
}
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// For brevity, use DP for each query. For large constraints, use a segment tree.
class Solution {
    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        final int MOD = 1_000_000_007;
        int ans = 0;
        for (int[] q : queries) {
            nums[q[0]] = q[1];
            int n = nums.length;
            int dp0 = 0, dp1 = nums[0];
            for (int i = 1; i < n; ++i) {
                int ndp0 = Math.max(dp0, dp1);
                int ndp1 = dp0 + nums[i];
                dp0 = ndp0; dp1 = ndp1;
            }
            int res = Math.max(dp0, dp1);
            ans = (ans + res) % MOD;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// For brevity, use DP for each query. For large constraints, use a segment tree.
class Solution {
    fun maximumSumSubsequence(nums: IntArray, queries: Array<IntArray>): Int {
        val MOD = 1_000_000_007
        var ans = 0
        for (q in queries) {
            nums[q[0]] = q[1]
            var dp0 = 0; var dp1 = nums[0]
            for (i in 1 until nums.size) {
                val ndp0 = maxOf(dp0, dp1)
                val ndp1 = dp0 + nums[i]
                dp0 = ndp0; dp1 = ndp1
            }
            val res = maxOf(dp0, dp1)
            ans = (ans + res) % MOD
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def maximumSumSubsequence(self, nums: list[int], queries: list[list[int]]) -> int:
        MOD = 10**9 + 7
        ans = 0
        for pos, x in queries:
            nums[pos] = x
            dp0, dp1 = 0, nums[0]
            for i in range(1, len(nums)):
                ndp0 = max(dp0, dp1)
                ndp1 = dp0 + nums[i]
                dp0, dp1 = ndp0, ndp1
            res = max(dp0, dp1)
            ans = (ans + res) % MOD
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn maximum_sum_subsequence(mut nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut ans = 0;
        for q in queries {
            nums[q[0] as usize] = q[1];
            let mut dp0 = 0;
            let mut dp1 = nums[0];
            for i in 1..nums.len() {
                let ndp0 = dp0.max(dp1);
                let ndp1 = dp0 + nums[i];
                dp0 = ndp0; dp1 = ndp1;
            }
            let res = dp0.max(dp1);
            ans = (ans + res) % MOD;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    maximumSumSubsequence(nums: number[], queries: number[][]): number {
        const MOD = 1e9 + 7;
        let ans = 0;
        for (const [pos, x] of queries) {
            nums[pos] = x;
            let dp0 = 0, dp1 = nums[0];
            for (let i = 1; i < nums.length; ++i) {
                const ndp0 = Math.max(dp0, dp1);
                const ndp1 = dp0 + nums[i];
                dp0 = ndp0; dp1 = ndp1;
            }
            const res = Math.max(dp0, dp1);
            ans = (ans + res) % MOD;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(qn) for the DP approach, or O((q+n) log n) for the segment tree approach. Each query updates and computes the answer.
  • 🧺 Space complexity: O(n) for the segment tree, or O(1) for the DP approach.