Is Maximum Sum of Subsequence With Non-adjacent Elements easy or hard?

The basic version of the problem is considered medium difficulty because it maps directly to a classic dynamic programming pattern. The LeetCode 3165 version becomes hard due to update queries that require segment trees and more complex state merging.

Maximum Sum of Subsequence With Non-adjacent Elements Python or Java solution

Both Python and Java implementations follow the same DP recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Python often uses two variables for constant space, while Java implementations typically use either a DP array or rolling variables for better performance.

What is the best approach for Maximum Sum of Subsequence With Non-adjacent Elements?

The most efficient approach is dynamic programming. Track the best sum including or excluding each element using the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]). This runs in O(n) time and can be optimized to O(1) space by keeping only the last two states.

What data structure is used in Maximum Sum of Subsequence With Non-adjacent Elements?

The base solution relies on dynamic programming with simple variables or arrays. In advanced versions that include update queries, a segment tree is used to maintain states for each range and merge them efficiently after updates.

What is the time complexity of Maximum Sum of Subsequence With Non-adjacent Elements?

The classic dynamic programming solution runs in O(n) time because each element is processed once. Space complexity can be O(n) with a DP array or O(1) using two rolling variables. If updates are involved and a segment tree is used, operations become O(log n) per update.

Is Maximum Sum of Subsequence With Non-adjacent Elements asked at Google, Amazon, or Meta?

Variants of this problem appear frequently in interviews at companies like Amazon, Google, and Meta. It is closely related to the classic House Robber problem and tests dynamic programming, state transitions, and optimization techniques.

Description Hints 2 Solution Video 1:01:19

3165. Maximum Sum of Subsequence With Non-adjacent Elements

Q: How to solve Maximum Sum of Subsequence With Non-adjacent Elements in O(n)?

Iterate through the array while maintaining two values: the best sum up to the previous index and the best sum up to two indices before. For each element compute max(prev1, prev2 + nums[i]). This ensures adjacent elements are never chosen and processes the entire array in linear time.

Hard15.7% acceptance2 companies

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⁵

Asked at 2 companies

Infosys

Google

Topics

Hints open one at a time

Hint 1

Can you solve each query in O(nums.length) with dynamic programming?

Hint 2

In order to optimize, we will use segment tree where each node contains the maximum value of (front element has been chosen or not, back element has been chosen or not).

1:01:19

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,5,9]
[[1,-2],[0,-3]]

Input

[0,-1]
[[0,-5]]

Your code is saved on this device.Solution