当前位置：首页 > article >正文

LeetCode 3165.不包含相邻元素的子序列的最大和：单点修改的线段树（动态规划）

article 2024/12/25 2:04:06

【LetMeFly】3165.不包含相邻元素的子序列的最大和：单点修改的线段树（动态规划）

力扣题目链接：https://leetcode.cn/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/

给你一个整数数组 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⁵

解题方法：线段树 + DP

对于单次操作，我们可以使用分治的方法来求解。对于一个子区间，我们比较关注的有：区间第一个元素是否被选取、区间最后一个元素是否被选取。也就是说，对于一个子区间，一共有以下4种情况：

开头一定不选，结尾一定不选，记为 $f 00$
开头一定不选，结尾可选(也可不选)，记为 $f 01$
开头可选(也可不选)，结尾一定不选，记为 $f 10$
开头可选(也可不选)，结尾可选(也可不选)，记为 $f 11$

那么对于区间 $[l e f t, r i g h t]$ ，如何进行分治操作呢？

如果 $l e f t == r i g h t$ ，那么这个区间就只有一个元素，这个区间的 $f 00 = f 01 = f 10 = 0$ ， $f11=\max(0, nums[left])$ 。
否则，令 $\lfloor\frac{left+right}{2}\rfloor$ ，递归计算 $[l e f t, mi d]$ 和 $[mi d + 1, r i g h t]$ 两个子区间的4个值并汇总得到这个区间的4个值。

假设左区间为 $p$ ，右区间为 $q$ ，则汇总方式为：
- $f00 = \max(f_p00+f_q10, f_p01+f_q00)$
- $f01 = \max(f_p00+f_q11, f_p01+f_q01)$
- $f10 = \max(f_p10+f_q10, f_p11+f_q00)$
- $f11 = \max(f_p10+f_q11, f_p11+f_q01)$

那么如何应对 $l e n (q u er i es)$ 次的修改呢？那就需要引入线段树了。

对于修改操作，使用线段树实现单点修改，线段树的每个节点维护对应区间的4个值
对于查询操作，线段树根节点（整个区间）的 $f 11$ 记为所求

时空复杂度分析

时间复杂度 $O(n+q\log n)$ ，其中 $n = l e n (n u m s)$ ， $q = l e n (q u er i es)$
空间复杂度 $O (n)$

AC代码

C++

const unsigned int mod = 1e9 + 7;

class Solution {
private:
    vector<array<unsigned int, 4>> tree;  // 00, 01, 10, 11

    void maintain(int index) {
        int leftIndex = 2 * index + 1;
        int rightIndex = 2 * index + 2;
        tree[index] = {
            max(tree[leftIndex][1] + tree[rightIndex][0], tree[leftIndex][0] + tree[rightIndex][2]),
            max(tree[leftIndex][0] + tree[rightIndex][3], tree[leftIndex][1] + tree[rightIndex][1]),
            max(tree[leftIndex][2] + tree[rightIndex][2], tree[leftIndex][3] + tree[rightIndex][0]),
            max(tree[leftIndex][2] + tree[rightIndex][3], tree[leftIndex][3] + tree[rightIndex][1])
        };
    }

    void buildTree(vector<int>& nums, int index, int left, int right) {
        if (left == right) {
            tree[index] = {0, 0, 0, (unsigned int)max(nums[left], 0)};
            return;
        }
        int mid = (left + right) / 2;
        buildTree(nums, 2 * index + 1, left, mid);
        buildTree(nums, 2 * index + 2, mid + 1, right);
        maintain(index);
    }

    void update(int index, int left, int right, int modifiedI, int val) {
        if (left == right) {
            tree[index][3] = max(0, val);
            return;
        }
        int mid = (left + right) / 2;
        if (modifiedI <= mid) {
            update(2 * index + 1, left, mid, modifiedI, val);
        } else {
            update(2 * index + 2, mid + 1, right, modifiedI, val);
        }
        maintain(index);
    }
public:
    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        tree.resize(nums.size() * 4);
        buildTree(nums, 0, 0, nums.size() - 1);
        unsigned int ans = 0;
        for (vector<int>& query : queries) {
            update(0, 0, nums.size() - 1, query[0], query[1]);
            ans = (ans + tree[0][3]) % mod;
        }
        return ans;
    }
};

Python

from typing import List

MOD = 1_000_000_007
class Solution:
    def maintain(self, index: int) -> None:
        leftNode = self.tree[2 * index + 1]
        rightNode = self.tree[2 * index + 2]
        self.tree[index] = [
            max(leftNode[0] + rightNode[2], leftNode[1] + rightNode[0]),
            max(leftNode[0] + rightNode[3], leftNode[1] + rightNode[1]),
            max(leftNode[2] + rightNode[2], leftNode[3] + rightNode[0]),
            max(leftNode[2] + rightNode[3], leftNode[3] + rightNode[1])
        ]
    
    def build(self, index: int, left: int, right: int) -> None:
        if left == right:
            self.tree[index][3] = self.nums[left]
            return
        mid = (left + right) >> 1
        self.build(2 * index + 1, left, mid)
        self.build(2 * index + 2, mid + 1, right)
        self.maintain(index)

    def update(self, index: int, left: int, right: int, modifiedI: int, val: int) -> None:
        if left == right:
            self.tree[index][3] = max(0, val)
            return
        mid = (left + right) >> 1
        if modifiedI <= mid:
            self.update(2 * index + 1, left, mid, modifiedI, val)
        else:
            self.update(2 * index + 2, mid + 1, right, modifiedI, val)
        self.maintain(index)

    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        self.tree = [[0, 0, 0, 0] for _ in range(len(nums) * 4)]  # 00, 01, 10, 11
        self.nums = nums
        self.build(0, 0, len(nums) - 1)
        ans = 0
        for q, v in queries:
            self.update(0, 0, len(nums) - 1, q, v)
            ans = (ans + self.tree[0][3]) % MOD
        return ans

Java

class Solution {
    private long[][] tree;  // 诶，如果不是long的话会有两组数据无法通过
    private final int mod = 1000000007;

    private void maintain(int index) {
        long[] leftNode = tree[2 * index + 1];
        long[] rightNode = tree[2 * index + 2];
        tree[index][0] = Math.max(leftNode[0] + rightNode[2], leftNode[1] + rightNode[0]);
        tree[index][1] = Math.max(leftNode[0] + rightNode[3], leftNode[1] + rightNode[1]);
        tree[index][2] = Math.max(leftNode[2] + rightNode[2], leftNode[3] + rightNode[0]);
        tree[index][3] = Math.max(leftNode[2] + rightNode[3], leftNode[3] + rightNode[1]);
    }

    private void build(int[] nums, int index, int left, int right) {
        if (left == right) {
            tree[index][3] = Math.max(0, nums[left]);
            return;
        }
        int mid = (left + right) / 2;
        build(nums, 2 * index + 1, left, mid);
        build(nums, 2 * index + 2, mid + 1, right);
        maintain(index);
    }

    private void update(int index, int left, int right, int modifiedI, int val) {
        if (left == right) {
            tree[index][3] = Math.max(0, val);
            return;
        }
        int mid = (left + right) / 2;
        if (modifiedI <= mid) {
            update(2 * index + 1, left, mid, modifiedI, val);
        } else {
            update(2 * index + 2, mid + 1, right, modifiedI, val);
        }
        maintain(index);
    }

    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        tree = new long[4 * nums.length][4];  // 00, 01, 10, 11
        build(nums, 0, 0, nums.length - 1);
        long ans = 0;
        for (int[] query : queries) {
            update(0, 0, nums.length - 1, query[0], query[1]);
            ans = (ans + tree[0][3]) % mod;
        }
        return (int)ans;
    }
}

Go

package main

type data struct {
    _00 int
    _01 int
    _10 int
    _11 int
}

type seg []data

func max(a int, b int) int {
    if a >= b {
        return a
    }
    return b
}

func maintain(tree seg, index int) {
    leftNode := tree[index * 2 + 1]
    rightNode := tree[index * 2 + 2]
    tree[index] = data{
        max(leftNode._00 + rightNode._10, leftNode._01 + rightNode._00),
        max(leftNode._00 + rightNode._11, leftNode._01 + rightNode._01),
        max(leftNode._10 + rightNode._10, leftNode._11 + rightNode._00),
        max(leftNode._10 + rightNode._11, leftNode._11 + rightNode._01),
    }
}

func build(tree seg, nums []int, index int, left int, right int) {
    if left == right {
        tree[index]._11 = max(0, nums[left])
        return
    }
    mid := (left + right) >> 1
    build(tree, nums, 2 * index + 1, left, mid)
    build(tree, nums, 2 * index + 2, mid + 1, right)
    maintain(tree, index)
}

func update(tree seg, index int, left int, right int, modified int, val int) {
    if left == right {
        tree[index]._11 = max(0, val)
        return
    }
    mid := (left + right) >> 1
    if modified <= mid {
        update(tree, 2 * index + 1, left, mid, modified, val)
    } else {
        update(tree, 2 * index + 2, mid + 1, right, modified, val)
    }
    maintain(tree, index)
}

func maximumSumSubsequence(nums []int, queries [][]int) int {
    tree := make(seg, len(nums) * 4)
    build(tree, nums, 0, 0, len(nums) - 1)
    ans := 0
    for _, query := range queries {
        update(tree, 0, 0, len(nums) - 1, query[0], query[1])
        ans = (ans + tree[0]._11) % 1_000_000_007
    }
    return ans
}