# Maximum Sum of Subsequence With Non-adjacent Elements
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-sum-of-subsequence-with-non-adjacent-elements)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-of-subsequence-with-non-adjacent-elements
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Segment Tree
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## 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** `109 + 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.

**Example 1:**

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

**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 * 104`
* `-105 <= nums[i] <= 105`
* `1 <= queries.length <= 5 * 104`
* `queries[i] == [posi, xi]`
* `0 <= posi <= nums.length - 1`
* `-105 <= xi <= 105`

# Approaches
## Brute Force: Re-computation for Each Query
This approach directly simulates the process described in the problem. For each query, it first modifies the `nums` array as specified. Then, it runs a dynamic programming algorithm to solve the classic "Maximum Sum of Non-adjacent Elements" problem (also known as the House Robber problem) on the entire updated array. The result of each query is added to a running total, which is returned modulo `10^9 + 7` at the end.
**Time:** O(Q * N), where Q is the number of queries and N is the length of `nums`. For each of the Q queries, we perform a linear scan of the array of size N. · **Space:** O(N) to store the input array `nums`. The DP calculation itself can be optimized to use O(1) auxiliary space.
**Pros:** Simple to understand and implement.; Correctly solves the problem for smaller inputs.
**Cons:** This approach is too slow for the given constraints and will result in a Time Limit Exceeded (TLE) error.; It performs a lot of redundant computations, as each query triggers a full recalculation over the entire array, even though only one element changes.
### Explanation
The core of this method is a linear-time dynamic programming solution for finding the maximum sum of a non-adjacent subsequence. Let's define two states for each element `i`:

*   `incl`: The maximum sum of a valid subsequence in `nums[0...i]` that **includes** `nums[i]`.
*   `excl`: The maximum sum of a valid subsequence in `nums[0...i]` that **excludes** `nums[i]`.

The recurrence relations are:
*   `incl[i] = excl[i-1] + nums[i]` (If we include `nums[i]`, we must have excluded `nums[i-1]`)
*   `excl[i] = max(incl[i-1], excl[i-1])` (If we exclude `nums[i]`, the max sum is simply the best we could do up to `nums[i-1]`)

We can optimize the space complexity of this DP from O(N) to O(1) by only keeping track of the `incl` and `excl` values from the previous step.

The overall algorithm iterates through each query, updates the array, and then applies this O(N) DP solution. The sum of results from all queries is accumulated.

```java
class Solution {
    private long calculateMaxSum(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        long incl = nums[0];
        long excl = 0;

        for (int i = 1; i < n; i++) {
            long new_excl = Math.max(incl, excl);
            long new_incl = excl + nums[i];
            
            excl = new_excl;
            incl = new_incl;
        }

        return Math.max(0L, Math.max(incl, excl));
    }

    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        long totalSum = 0;
        int MOD = 1_000_000_007;

        for (int[] query : queries) {
            int pos = query[0];
            int val = query[1];
            nums[pos] = val;
            totalSum = (totalSum + calculateMaxSum(nums));
        }

        return (int) (totalSum % MOD);
    }
}
```
### Algorithm
*   Initialize a variable `totalSum` to 0 and `MOD = 10^9 + 7`.
*   Iterate through each query `[pos, x]` in the `queries` array.
    *   Update the input array: `nums[pos] = x`.
    *   Calculate the maximum non-adjacent subsequence sum for the modified `nums` array. This is the core "House Robber" problem.
        *   Initialize two variables, `incl` and `excl`, to track the maximum sum including and excluding the current element, respectively.
        *   `excl = 0`, `incl = nums[0]` (for the first element).
        *   Iterate from the second element (`i = 1` to `n-1`):
            *   Calculate `new_excl = max(incl, excl)`. This is the max sum up to `i-1`.
            *   Calculate `new_incl = excl + nums[i]`. This is the max sum up to `i-1` excluding `nums[i-1]`, plus `nums[i]`.
            *   Update `excl = new_excl` and `incl = new_incl`.
        *   The maximum sum for the current array is `max(0, incl, excl)`.
    *   Add the calculated maximum sum to `totalSum`.
*   After processing all queries, return `totalSum % MOD`.

## Segment Tree with DP State Matrix
A much more efficient approach utilizes a segment tree. The key idea is to store DP state information in each node of the tree. Since a simple sum or max is not enough to combine adjacent segments, we store a 2x2 matrix in each node. This matrix encapsulates the four possible maximum sums for the subarray corresponding to that node, based on whether the first and last elements of the subarray are included in the subsequence.
**Time:** O(N + Q * log N). O(N) is required for the initial build of the segment tree. Each of the Q queries involves an update operation, which takes O(log N) time. · **Space:** O(N) to store the segment tree. The tree has approximately 4N nodes, and each node stores a constant amount of information (a 4-element array).
**Pros:** Highly efficient, with logarithmic time complexity per query.; Scales well for a large number of queries and a large array size.; It's a general technique that can be adapted for other DP problems with local dependencies and point updates.
**Cons:** Significantly more complex to implement than the brute-force approach.; The logic for the matrix states and the merge operation must be perfectly correct to yield the right answer.
### Explanation
Each node in the segment tree will cover a range `[i, j]` of the `nums` array and store a 2x2 matrix `M` where:
*   `M[0][0]`: Max sum in `nums[i...j]`, neither `nums[i]` nor `nums[j]` is selected.
*   `M[0][1]`: Max sum in `nums[i...j]`, `nums[j]` is selected, but `nums[i]` is not.
*   `M[1][0]`: Max sum in `nums[i...j]`, `nums[i]` is selected, but `nums[j]` is not.
*   `M[1][1]`: Max sum in `nums[i...j]`, both `nums[i]` and `nums[j]` are selected.

A leaf node for a single element `nums[k]` has a matrix `[[0, -inf], [-inf, nums[k]]]`, where `-inf` is a very small number representing an impossible state.

The crucial part is the `merge` operation. When combining a left child's matrix `L` and a right child's matrix `R`, we can compute the parent's matrix `M` by considering all valid combinations that respect the non-adjacent rule between the end of the left segment and the start of the right segment.

With this structure, an update to `nums[pos]` only requires updating the leaf for `pos` and its ancestors up to the root, which takes O(log N) time. The answer for the whole array is always available at the root node.

```java
class Solution {
    // A 2x2 matrix representing the 4 DP states.
    // M[0][0]=dp00, M[0][1]=dp01, M[1][0]=dp10, M[1][1]=dp11
    long[][] tree;
    int[] nums;
    int n;
    long INF = (long) -1e18; // Using a large negative number for impossible states

    private long[] merge(long[] left, long[] right) {
        long[] res = new long[4];
        long l00 = left[0], l01 = left[1], l10 = left[2], l11 = left[3];
        long r00 = right[0], r01 = right[1], r10 = right[2], r11 = right[3];

        // res[0] = dp00
        res[0] = Math.max(l00 + r00, Math.max(l00 + r10, l01 + r00));
        // res[1] = dp01
        res[1] = Math.max(l00 + r01, Math.max(l00 + r11, l01 + r01));
        // res[2] = dp10
        res[2] = Math.max(l10 + r00, Math.max(l10 + r10, l11 + r00));
        // res[3] = dp11
        res[3] = Math.max(l10 + r01, Math.max(l10 + r11, l11 + r01));
        return res;
    }

    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = new long[]{0, INF, INF, nums[start]};
            return;
        }
        int mid = start + (end - start) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            nums[idx] = val;
            tree[node] = new long[]{0, INF, INF, val};
            return;
        }
        int mid = start + (end - start) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        this.nums = nums;
        this.n = nums.length;
        this.tree = new long[4 * n][];
        build(1, 0, n - 1);

        long totalSum = 0;
        int MOD = 1_000_000_007;

        for (int[] query : queries) {
            update(1, 0, n - 1, query[0], query[1]);
            long[] root = tree[1];
            long ans = Math.max(0L, Math.max(root[0], Math.max(root[1], Math.max(root[2], root[3]))));
            totalSum = (totalSum + ans);
        }

        return (int) (totalSum % MOD);
    }
}
```
### Algorithm
*   Define a structure (e.g., a class or a `long[]` array) to represent a 2x2 matrix for DP states. Let `matrix[i][j]` store the max sum where `i=1` means the first element of the range is taken and `j=1` means the last element is taken.
*   Implement a `merge(left_matrix, right_matrix)` function. This function combines the DP states of two adjacent segments, respecting the non-adjacent constraint at the boundary. The formula for the new matrix `M` from left `L` and right `R` is `M[i][j] = max(L[i][0] + R[0][j], L[i][0] + R[1][j], L[i][1] + R[0][j])`.
*   Implement a `build` function to construct the segment tree. For a leaf node at index `k`, the matrix is `[[0, -inf], [-inf, nums[k]]]`. Internal nodes are built by merging their children.
*   Implement an `update` function. When `nums[pos]` changes, it updates the corresponding leaf's matrix and propagates the changes up to the root by re-merging nodes along the path.
*   Initialize `totalSum = 0` and `MOD = 10^9 + 7`.
*   Build the segment tree on the initial `nums` array.
*   For each query `[pos, x]`:
    *   Call the `update` function to modify the tree.
    *   The matrix at the root of the tree now holds the DP states for the entire updated array.
    *   The answer for the query is the maximum value among the four entries of the root's matrix, also compared with 0 (for an empty subsequence).
    *   Add this answer to `totalSum`.
*   Return `totalSum % MOD`.

# Solutions
### Java

```java
class Node { int l , r ; long s00 , s01 , s10 , s11 ; Node ( int l , int r ) { this . l = l ; this . r = r ; this . s00 = this . s01 = this . s10 = this . s11 = 0 ; } } class SegmentTree { Node [] tr ; SegmentTree ( int n ) { tr = new Node [ n * 4 ]; build ( 1 , 1 , n ); } void build ( int u , int l , int r ) { tr [ u ] = new Node ( l , r ); if ( l == r ) { return ; } int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); } long query ( int u , int l , int r ) { if ( tr [ u ]. l >= l && tr [ u ]. r <= r ) { return tr [ u ]. s11 ; } int mid = ( tr [ u ]. l + tr [ u ]. r ) >> 1 ; long ans = 0 ; if ( r <= mid ) { ans = query ( u << 1 , l , r ); } if ( l > mid ) { ans = Math . max ( ans , query ( u << 1 | 1 , l , r )); } return ans ; } void pushup ( int u ) { Node left = tr [ u << 1 ]; Node right = tr [ u << 1 | 1 ]; tr [ u ]. s00 = Math . max ( left . s00 + right . s10 , left . s01 + right . s00 ); tr [ u ]. s01 = Math . max ( left . s00 + right . s11 , left . s01 + right . s01 ); tr [ u ]. s10 = Math . max ( left . s10 + right . s10 , left . s11 + right . s00 ); tr [ u ]. s11 = Math . max ( left . s10 + right . s11 , left . s11 + right . s01 ); } void modify ( int u , int x , int v ) { if ( tr [ u ]. l == tr [ u ]. r ) { tr [ u ]. s11 = Math . max ( 0 , v ); return ; } int mid = ( tr [ u ]. l + tr [ u ]. r ) >> 1 ; if ( x <= mid ) { modify ( u << 1 , x , v ); } else { modify ( u << 1 | 1 , x , v ); } pushup ( u ); } } class Solution { public int maximumSumSubsequence ( int [] nums , int [][] queries ) { int n = nums . length ; SegmentTree tree = new SegmentTree ( n ); for ( int i = 0 ; i < n ; ++ i ) { tree . modify ( 1 , i + 1 , nums [ i ]); } long ans = 0 ; final int mod = ( int ) 1 e9 + 7 ; for ( int [] q : queries ) { tree . modify ( 1 , q [ 0 ] + 1 , q [ 1 ]); ans = ( ans + tree . query ( 1 , 1 , n )) % mod ; } return ( int ) ans ; } }
```

### CPP

```cpp
class Node { public: int l , r ; long long s00 , s01 , s10 , s11 ; Node ( int l , int r ) : l ( l ) , r ( r ) , s00 ( 0 ) , s01 ( 0 ) , s10 ( 0 ) , s11 ( 0 ) {} }; class SegmentTree { public: vector < Node *> tr ; SegmentTree ( int n ) : tr ( n << 2 ) { build ( 1 , 1 , n ); } void build ( int u , int l , int r ) { tr [ u ] = new Node ( l , r ); if ( l == r ) { return ; } int mid = ( l + r ) >> 1 ; build ( u << 1 , l , mid ); build ( u << 1 | 1 , mid + 1 , r ); } long long query ( int u , int l , int r ) { if ( tr [ u ] -> l >= l && tr [ u ] -> r <= r ) { return tr [ u ] -> s11 ; } int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; long long ans = 0 ; if ( r <= mid ) { ans = query ( u << 1 , l , r ); } if ( l > mid ) { ans = max ( ans , query ( u << 1 | 1 , l , r )); } return ans ; } void pushup ( int u ) { Node * left = tr [ u << 1 ]; Node * right = tr [ u << 1 | 1 ]; tr [ u ] -> s00 = max ( left -> s00 + right -> s10 , left -> s01 + right -> s00 ); tr [ u ] -> s01 = max ( left -> s00 + right -> s11 , left -> s01 + right -> s01 ); tr [ u ] -> s10 = max ( left -> s10 + right -> s10 , left -> s11 + right -> s00 ); tr [ u ] -> s11 = max ( left -> s10 + right -> s11 , left -> s11 + right -> s01 ); } void modify ( int u , int x , int v ) { if ( tr [ u ] -> l == tr [ u ] -> r ) { tr [ u ] -> s11 = max ( 0LL , ( long long ) v ); return ; } int mid = ( tr [ u ] -> l + tr [ u ] -> r ) >> 1 ; if ( x <= mid ) { modify ( u << 1 , x , v ); } else { modify ( u << 1 | 1 , x , v ); } pushup ( u ); } ~ SegmentTree () { for ( auto node : tr ) { delete node ; } } }; class Solution { public: int maximumSumSubsequence ( vector < int >& nums , vector < vector < int >>& queries ) { int n = nums . size (); SegmentTree tree ( n ); for ( int i = 0 ; i < n ; ++ i ) { tree . modify ( 1 , i + 1 , nums [ i ]); } long long ans = 0 ; const int mod = 1e9 + 7 ; for ( const auto & q : queries ) { tree . modify ( 1 , q [ 0 ] + 1 , q [ 1 ]); ans = ( ans + tree . query ( 1 , 1 , n )) % mod ; } return ( int ) ans ; } };
```

### Python

```python
def max ( a : int , b : int ) -> int : return a if a > b else b class Node : __slots__ = "l" , "r" , "s00" , "s01" , "s10" , "s11" def __init__ ( self , l : int , r : int ): self . l = l self . r = r self . s00 = self . s01 = self . s10 = self . s11 = 0 class SegmentTree : __slots__ = "tr" def __init__ ( self , n : int ): self . tr : List [ Node | None ] = [ None ] * ( n << 2 ) self . build ( 1 , 1 , n ) def build ( self , u : int , l : int , r : int ): self . tr [ u ] = Node ( l , r ) if l == r : return mid = ( l + r ) >> 1 self . build ( u << 1 , l , mid ) self . build ( u << 1 | 1 , mid + 1 , r ) def query ( self , u : int , l : int , r : int ) -> int : if self . tr [ u ]. l >= l and self . tr [ u ]. r <= r : return self . tr [ u ]. s11 mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 ans = 0 if r <= mid : ans = self . query ( u << 1 , l , r ) if l > mid : ans = max ( ans , self . query ( u << 1 | 1 , l , r )) return ans def pushup ( self , u : int ): left , right = self . tr [ u << 1 ], self . tr [ u << 1 | 1 ] self . tr [ u ]. s00 = max ( left . s00 + right . s10 , left . s01 + right . s00 ) self . tr [ u ]. s01 = max ( left . s00 + right . s11 , left . s01 + right . s01 ) self . tr [ u ]. s10 = max ( left . s10 + right . s10 , left . s11 + right . s00 ) self . tr [ u ]. s11 = max ( left . s10 + right . s11 , left . s11 + right . s01 ) def modify ( self , u : int , x : int , v : int ): if self . tr [ u ]. l == self . tr [ u ]. r : self . tr [ u ]. s11 = max ( 0 , v ) return mid = ( self . tr [ u ]. l + self . tr [ u ]. r ) >> 1 if x <= mid : self . modify ( u << 1 , x , v ) else : self . modify ( u << 1 | 1 , x , v ) self . pushup ( u ) class Solution : def maximumSumSubsequence ( self , nums : List [ int ], queries : List [ List [ int ]]) -> int : n = len ( nums ) tree = SegmentTree ( n ) for i , x in enumerate ( nums , 1 ): tree . modify ( 1 , i , x ) ans = 0 mod = 10 ** 9 + 7 for i , x in queries : tree . modify ( 1 , i + 1 , x ) ans = ( ans + tree . query ( 1 , 1 , n )) % mod return ans
```