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] <= 1051 <= queries.length <= 5 * 104queries[i] == [posi, xi]0 <= posi <= nums.length - 1-105 <= xi <= 105Problem Overview: Given an integer array, select a subsequence of elements such that no two chosen elements are adjacent and the total sum is maximized. Some variants also include update queries where array values change and the maximum non‑adjacent subsequence sum must be recomputed efficiently.
Approach 1: Recursive with Memoization (Top‑Down DP) (Time: O(n), Space: O(n))
This approach models the problem as a decision at each index: either take the current element and skip the next one, or skip the current element entirely. A recursive function explores both choices. Memoization stores results for each index so the same subproblem is not recomputed. The recurrence is dp[i] = max(nums[i] + dp[i+2], dp[i+1]). This method is useful for understanding the structure of the problem and how overlapping subproblems arise in dynamic programming.
Approach 2: Iterative Dynamic Programming (Bottom‑Up) (Time: O(n), Space: O(n))
The recursive recurrence can be converted into a bottom‑up DP table. Iterate through the array while maintaining the best sum achievable up to each index. For each position i, compute dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The value dp[i-1] represents skipping the element, while dp[i-2] + nums[i] represents taking it. This version avoids recursion overhead and is commonly used in interview settings because it clearly shows the transition logic.
Approach 3: Optimized Dynamic Programming with Prefix State (Time: O(n), Space: O(1))
The DP table only depends on the previous two states, so storing the entire array is unnecessary. Maintain two variables: prev1 (best sum up to previous index) and prev2 (best sum up to index‑2). For each element, compute current = max(prev1, prev2 + nums[i]). Then shift the variables forward. This reduces memory to constant space while keeping the same O(n) time complexity. It is the most practical implementation for the classic non‑adjacent subsequence problem.
Approach 4: Segment Tree for Dynamic Updates (Time: O((n + q) log n), Space: O(n))
When the array receives updates and the maximum non‑adjacent subsequence sum must be recomputed after each change, a segment tree becomes effective. Each node stores multiple states representing whether the segment starts or ends with a chosen element. During merges, these states combine while respecting the non‑adjacent constraint. Updates modify a single index and propagate upward in O(log n). This technique handles large numbers of queries efficiently while maintaining correct subsequence constraints.
Recommended for interviews: Start with the recursive recurrence to demonstrate understanding of the decision process. Interviewers usually expect the iterative dynamic programming solution with O(n) time and O(1) space. If the problem includes update queries, recognizing that a segment tree with state merging is required demonstrates stronger algorithmic design skills.
The key idea here is to use dynamic programming to compute the maximum sum of a subsequence of non-adjacent elements. Instead of recalculating the maximum sum from scratch after each query, we can maintain the results using the following:
include - the maximum sum including the current element; and exclude - the maximum sum excluding the current element.i, update include and exclude based on the previous values.This Python solution follows the dynamic programming approach for calculating the maximum sum of non-adjacent elements. For each query, it updates the nums array, computes the maximum sum of the sequence using helper values, and accumulates to result with modulo operation for large numbers.
Python
Time Complexity: O(n * m).
Space Complexity: O(1), where n is the length of nums and m is the number of queries. The space complexity is constant because no additional data structures are used beyond variables.
This solution involves using prefix sums to improve the efficiency of queries. We maintain the same idea of 'include' and 'exclude' sums but update them as changes occur from queries instead of recalculating all values from scratch after each query.
This Java solution uses a more optimized dynamic programming approach with prefix sums. It initializes the maximum sum for non-adjacent subsequence and recalculates it when every query updates an element. It maintains cumulative sums using a dynamic programming array.
Java
Time Complexity: O(n * m).
Space Complexity: O(n), where n is the length of nums and m is the number of queries.
This approach involves using dynamic programming to compute the maximum sum of non-adjacent elements. We'll maintain two variables to keep track of the maximum sum including and excluding the current element. With each query update, we'll recompute the maximum sum since the array changes.
The solution iteratively updates the 'nums' array with each query. For each array configuration, it calculates the maximum sum of non-adjacent elements using dynamic programming, utilizing 'include' and 'exclude' variables. The result is accumulated for all queries and finally printed modulo 109 + 7.
Time Complexity: O(N * Q), where N is the length of the array and Q is the number of queries.
Space Complexity: O(1), uses a constant amount of space.
This approach uses recursion combined with memoization. By using a recursive function to attempt including or excluding the current element, memoization is employed to store results of previously computed states, thereby optimizing repeated calculations.
This C solution utilizes a recursive function (dfs) to navigate the number list, deciding to include or exclude each element, thus computing potential maximum sums. Memoization optimizes recursive calls by caching previously computed results, leading to time efficiency.
Time Complexity: O(N * Q), where N is the number of elements in nums and Q is the number of queries.
Space Complexity: O(N), due to the memoization array.
According to the problem description, we need to perform multiple point updates and range queries. In this scenario, we consider using a segment tree to solve the problem.
First, we define a Node class to store the information of the segment tree nodes, including the left and right endpoints l and r, as well as four state values s_{00}, s_{01}, s_{10}, and s_{11}. Specifically:
s_{00} represents the maximum sum of the subsequence that does not include the left and right endpoints of the current node;s_{01} represents the maximum sum of the subsequence that does not include the left endpoint of the current node;s_{10} represents the maximum sum of the subsequence that does not include the right endpoint of the current node;s_{11} represents the maximum sum of the subsequence that includes the left and right endpoints of the current node.Next, we define a SegmentTree class to construct the segment tree. During the construction of the segment tree, we need to recursively build the left and right subtrees and update the state values of the current node based on the state values of the left and right subtrees.
In the main function, we first construct the segment tree based on the given array nums and process each query. For each query, we first perform a point update, then query the state values of the entire range, and accumulate the result into the answer.
The time complexity is O((n + q) times log n), and the space complexity is O(n). Here, n represents the length of the array nums, and q represents the number of queries.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Solution | Time Complexity: O(n * m). |
| Optimized Dynamic Programming with Prefix Sum | Time Complexity: O(n * m). |
| Iterative Dynamic Programming (DP) Approach | Time Complexity: O(N * Q), where N is the length of the array and Q is the number of queries. |
| Recursive with Memoization Approach | Time Complexity: O(N * Q), where N is the number of elements in nums and Q is the number of queries. |
| Segment Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n) | O(n) | Understanding the decision tree and DP recurrence |
| Iterative Dynamic Programming | O(n) | O(n) | Standard DP implementation for arrays |
| Space Optimized DP | O(n) | O(1) | Best practical solution when only the final result is required |
| Segment Tree with State Merging | O((n + q) log n) | O(n) | When the array receives updates and queries must be answered repeatedly |
3165. Maximum Sum of Subsequence With Non-adjacent Elements | Bonus Qs + Hint | Weekly Leetcode 399 • codingMohan • 2,361 views views
Watch 5 more video solutions →Practice Maximum Sum of Subsequence With Non-adjacent Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor