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.

#3165

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

不包含相邻元素的子序列的最大和

给你一个整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [pos i , x i ] 。对于每个查询 i ，首先将 nums[pos i ] 设置为 x i ，然后计算查询 i 的答案，该答案为 nums 中不包含相邻元素的子序列的最大和。返回所…

数组分治动态规划线段树

题目描述

给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [pos_i, x_i]。

对于每个查询 i，首先将 nums[pos_i] 设置为 x_i，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素 的子序列的最大和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 10⁹ + 7 取余的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

示例 1：

输入：nums = [3,5,9], queries = [[1,-2],[0,-3]]

输出：21

解释：
执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。
执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。

示例 2：

输入：nums = [0,-1], queries = [[0,-5]]

输出：0

解释：
执行第 1 个查询后，nums = [-5,-1]，不包含相邻元素的子序列的最大和为 0（选择空子序列）。

提示：

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⁵

lightbulb

解题思路

方法一：线段树

根据题目描述，我们需要进行多次单点修改和区间查询，这种场景下，我们考虑使用线段树来解决。

首先，我们定义一个 $\textit{Node}$ 类，用于存储线段树的节点信息，包括左右端点 $l$ 和 $r$ ，以及四个状态值 $s_{00}$ , $s_{01}$ , $s_{10}$ 和 $s_{11}$ 。其中：

$s_{00}$ 表示不包含当前节点左右端点的子序列的最大和；
$s_{01}$ 表示不包含当前节点左端点的子序列的最大和；
$s_{10}$ 表示不包含当前节点右端点的子序列的最大和；
$s_{11}$ 表示包含当前节点左右端点的子序列的最大和。

接着，我们定义一个 $\textit{SegmentTree}$ 类，用于构建线段树。在构建线段树的过程中，我们需要递归地构建左右子树，并根据左右子树的状态值来更新当前节点的状态值。

在主函数中，我们首先根据给定的数组 $\textit{nums}$ 构建线段树，并对每个查询进行处理。对于每个查询，我们首先进行单点修改，然后查询整个区间的状态值，并将结果累加到答案中。

时间复杂度 $O((n + q) \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 表示数组 $\textit{nums}$ 的长度，而 $q$ 表示查询的次数。

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

71

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2407 最长递增子序列 II #3117 划分数组得到最小的值之和 #3291 形成目标字符串需要的最少字符串数 I