Maximum Sum of Subsequence With Non-adjacent Elements

Hard

#2812Time: 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.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

You are given an array nums consisting of integers. You are also given a 2D array queries, where queries[i] = [pos_i, x_i].

For query i, we first set nums[pos_i] equal to x_i, 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⁹ + 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 1^st query, nums = [3,-2,9] and the maximum sum of a subsequence with non-adjacent elements is 3 + 9 = 12.
After the 2^nd 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 1^st 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⁴
-10⁵ <= nums[i] <= 10⁵
1 <= queries.length <= 5 * 10⁴
queries[i] == [pos_i, x_i]
0 <= pos_i <= nums.length - 1
-10⁵ <= x_i <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    private long calculateMaxSum(int[] nums) {3        int n = nums.length;4        if (n == 0) {5            return 0;6        }7 8        long incl = nums[0];9        long excl = 0;10 11        for (int i = 1; i < n; i++) {12            long new_excl = Math.max(incl, excl);13            long new_incl = excl + nums[i];14            15            excl = new_excl;16            incl = new_incl;17        }18 19        return Math.max(0L, Math.max(incl, excl));20    }21 22    public int maximumSumSubsequence(int[] nums, int[][] queries) {23        long totalSum = 0;24        int MOD = 1_000_000_007;25 26        for (int[] query : queries) {27            int pos = query[0];28            int val = query[1];29            nums[pos] = val;30            totalSum = (totalSum + calculateMaxSum(nums));31        }32 33        return (int) (totalSum % MOD);34    }35}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    // A 2x2 matrix representing the 4 DP states.3    // M[0][0]=dp00, M[0][1]=dp01, M[1][0]=dp10, M[1][1]=dp114    long[][] tree;5    int[] nums;6    int n;7    long INF = (long) -1e18; // Using a large negative number for impossible states8 9    private long[] merge(long[] left, long[] right) {10        long[] res = new long[4];11        long l00 = left[0], l01 = left[1], l10 = left[2], l11 = left[3];12        long r00 = right[0], r01 = right[1], r10 = right[2], r11 = right[3];13 14        // res[0] = dp0015        res[0] = Math.max(l00 + r00, Math.max(l00 + r10, l01 + r00));16        // res[1] = dp0117        res[1] = Math.max(l00 + r01, Math.max(l00 + r11, l01 + r01));18        // res[2] = dp1019        res[2] = Math.max(l10 + r00, Math.max(l10 + r10, l11 + r00));20        // res[3] = dp1121        res[3] = Math.max(l10 + r01, Math.max(l10 + r11, l11 + r01));22        return res;23    }24 25    private void build(int node, int start, int end) {26        if (start == end) {27            tree[node] = new long[]{0, INF, INF, nums[start]};28            return;29        }30        int mid = start + (end - start) / 2;31        build(2 * node, start, mid);32        build(2 * node + 1, mid + 1, end);33        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);34    }35 36    private void update(int node, int start, int end, int idx, int val) {37        if (start == end) {38            nums[idx] = val;39            tree[node] = new long[]{0, INF, INF, val};40            return;41        }42        int mid = start + (end - start) / 2;43        if (start <= idx && idx <= mid) {44            update(2 * node, start, mid, idx, val);45        } else {46            update(2 * node + 1, mid + 1, end, idx, val);47        }48        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);49    }50 51    public int maximumSumSubsequence(int[] nums, int[][] queries) {52        this.nums = nums;53        this.n = nums.length;54        this.tree = new long[4 * n][];55        build(1, 0, n - 1);56 57        long totalSum = 0;58        int MOD = 1_000_000_007;59 60        for (int[] query : queries) {61            update(1, 0, n - 1, query[0], query[1]);62            long[] root = tree[1];63            long ans = Math.max(0L, Math.max(root[0], Math.max(root[1], Math.max(root[2], root[3]))));64            totalSum = (totalSum + ans);65        }66 67        return (int) (totalSum % MOD);68    }69}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1def 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem