#3165

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Sum of Subsequence With Non-adjacent Elements

Compute the maximum sum of a subsequence where no two adjacent elements are selected after each array update efficiently using DP.

array divide and conquer dynamic programming segment tree

Problem Statement

You are given an integer array nums and a 2D array queries where queries[i] = [posi, xi]. For each query, replace nums[posi] with xi and then compute the maximum sum of a subsequence in nums such that no two selected elements are adjacent.

Return the sum of the maximum sums obtained after executing all queries. The solution must handle large arrays efficiently and account for negative values where choosing an empty subsequence might be optimal.

Examples

Example 1

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

Output: 21

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

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

Solution Approach

Dynamic Programming with State Transition

Maintain two states for each element: include and exclude. Update these states as you iterate through nums to compute the maximum sum of non-adjacent elements. For each query, apply the change and recalculate the states efficiently using the previous computation.

Segment Tree Optimization

Use a segment tree to store include and exclude values for array segments. This allows each query to update a value and recalculate the maximum sum in logarithmic time relative to nums.length, avoiding full recomputation for large arrays.

Handling Negative and Zero Values

When nums contain negative numbers, the optimal non-adjacent subsequence may skip certain elements entirely. Track the maximum sum carefully to ensure empty subsequences are considered when all numbers are negative.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The naive approach recalculates the maximum sum for each query in O(nums.length), leading to O(nums.length * queries.length). Using segment trees or incremental DP updates reduces time complexity closer to O((nums.length + queries.length) * log(nums.length)) with O(nums.length) space for state tracking.

What Interviewers Usually Probe

The problem is testing your ability to maintain state dynamically after array updates.
Expect hints towards using DP with careful state transitions or a segment tree to avoid recomputation.
Watch for edge cases with negative numbers or empty subsequences.

Common Pitfalls or Variants

Common pitfalls

Recomputing the entire array from scratch after each query causing TLE.
Ignoring the empty subsequence option when all elements are negative.
Incorrectly updating adjacent states leading to invalid subsequences.

Follow-up variants

Compute maximum sum of non-adjacent elements with a fixed number of selections per query.
Allow selecting elements with at least k spacing between them instead of just one.
Queries that incrementally add to elements instead of replacing them, requiring cumulative DP updates.

FAQ

How does the state transition dynamic programming pattern apply here?

Use two states per element: one including it in the sum and one excluding it, updating these states sequentially to maintain the maximum sum without adjacent elements.

Can this problem be solved faster than recomputing for each query?

Yes, segment trees or incremental DP updates allow each query to modify the state and recalculate the maximum sum efficiently.

What if all elements in nums are negative?

The optimal subsequence may be empty, so always consider a sum of zero when all elements are negative.

Does the solution support large arrays efficiently?

With segment trees or careful DP state tracking, the solution scales to arrays up to 5 * 10^4 elements.

Is this pattern useful for other subsequence problems?

Yes, any problem requiring maximum sums of subsequences with adjacency constraints can leverage state transition DP or segment tree optimizations.

terminal

Solution

Solution 1: Segment Tree

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.

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

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

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

Continue Practicing

#2407 longest increasing subsequence ii #3117 minimum sum of values by dividing array #3291 minimum number of valid strings to form target i