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

news/2024/12/28 2:46:48/

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

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

给你一个整数数组 nums 和一个二维数组 queries,其中 queries[i] = [posi, xi]

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

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

由于最终答案可能非常大,返回其对 109 + 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 * 104
  • -105 <= nums[i] <= 105
  • 1 <= queries.length <= 5 * 104
  • queries[i] == [posi, xi]
  • 0 <= posi <= nums.length - 1
  • -105 <= xi <= 105

解题方法:线段树 + DP

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

  • 开头一定不选,结尾一定不选,记为 f 00 f00 f00
  • 开头一定不选,结尾可选(也可不选),记为 f 01 f01 f01
  • 开头可选(也可不选),结尾一定不选,记为 f 10 f10 f10
  • 开头可选(也可不选),结尾可选(也可不选),记为 f 11 f11 f11

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

  • 如果 l e f t = = r i g h t left==right left==right,那么这个区间就只有一个元素,这个区间的 f 00 = f 01 = f 10 = 0 f00=f01=f10=0 f00=f01=f10=0 f 11 = max ⁡ ( 0 , n u m s [ l e f t ] ) f11=\max(0, nums[left]) f11=max(0,nums[left])

  • 否则,令 m i d = ⌊ l e f t + r i g h t 2 ⌋ mid = \lfloor\frac{left+right}{2}\rfloor mid=2left+right,递归计算 [ l e f t , m i d ] [left, mid] [left,mid] [ m i d + 1 , r i g h t ] [mid + 1, right] [mid+1,right]两个子区间的4个值并汇总得到这个区间的4个值。

    假设左区间为 p p p,右区间为 q q q,则汇总方式为:

    • f 00 = max ⁡ ( f p 00 + f q 10 , f p 01 + f q 00 ) f00 = \max(f_p00+f_q10, f_p01+f_q00) f00=max(fp00+fq10,fp01+fq00)
    • f 01 = max ⁡ ( f p 00 + f q 11 , f p 01 + f q 01 ) f01 = \max(f_p00+f_q11, f_p01+f_q01) f01=max(fp00+fq11,fp01+fq01)
    • f 10 = max ⁡ ( f p 10 + f q 10 , f p 11 + f q 00 ) f10 = \max(f_p10+f_q10, f_p11+f_q00) f10=max(fp10+fq10,fp11+fq00)
    • f 11 = max ⁡ ( f p 10 + f q 11 , f p 11 + f q 01 ) f11 = \max(f_p10+f_q11, f_p11+f_q01) f11=max(fp10+fq11,fp11+fq01)

那么如何应对 l e n ( q u e r i e s ) len(queries) len(queries)次的修改呢?那就需要引入线段树了。

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

时空复杂度分析

  • 时间复杂度 O ( n + q log ⁡ n ) O(n+q\log n) O(n+qlogn),其中 n = l e n ( n u m s ) n=len(nums) n=len(nums) q = l e n ( q u e r i e s ) q=len(queries) q=len(queries)
  • 空间复杂度 O ( n ) O(n) O(n)

AC代码

C++
const unsigned int mod = 1e9 + 7;class Solution {
private:vector<array<unsigned int, 4>> tree;  // 00, 01, 10, 11void 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 ListMOD = 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]returnmid = (left + right) >> 1self.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)returnmid = (left + right) >> 1if 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, 11self.nums = numsself.build(0, 0, len(nums) - 1)ans = 0for q, v in queries:self.update(0, 0, len(nums) - 1, q, v)ans = (ans + self.tree[0][3]) % MODreturn 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, 11build(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 maintype data struct {_00 int_01 int_10 int_11 int
}type seg []datafunc 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) >> 1build(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) >> 1if 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 := 0for _, 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
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/143452715


http://www.ppmy.cn/news/1544320.html

相关文章

如何使用Google Search Console进行关键词研究[4 种简便方法]

关键词研究是任何成功的 SEO 策略的基础要素。 通过确定正确的关键词&#xff0c;您可以更好地了解受众正在搜索什么&#xff0c;创建符合他们意图的内容&#xff0c;并为您的网站带来更多目标流量。 虽然有许多付费工具可用&#xff0c;但您可以选择 Google Search Console …

线程数组一例

下面是一个示例代码&#xff0c;展示了如何使用 C 的 std::thread 并发创建一组线程&#xff0c;并且每个线程完成一个大运算的一部分。在这个示例中&#xff0c;我们使用 OpenMP 来加速每个线程内部的运算&#xff0c;最后等待所有线程完成。 示例代码 #include <iostrea…

ASPICE 4.0引领自动驾驶未来:机器学习模型的特点与实践

ASPICE 4.0-ML机器学习模型是针对汽车行业&#xff0c;特别是在汽车软件开发中&#xff0c;针对机器学习&#xff08;Machine Learning, ML&#xff09;应用的特定标准和过程。ASPICE&#xff08;Automotive SPICE&#xff09;是一种基于软件控制的系统开发过程的国际标准&…

python的数据结构列表方法及扩展(栈和队列)

python的数据结构 python的list方法 list.append() 添加一个元素到列表末尾。list,append(num)相当于a[len(a):] [num] a [1,2,3,4,5] a.append(6) print(a) a[len(a):] [7] print(a)list.extend() 添加指定列表的所有元素。list.extend(nums)相当于a a nums a [1,2,3]…

教你快速学会新媒体运营,你必须掌握的新媒体应用分别有哪些,详细介绍这些应用都有哪些功能和特点,快收藏吧!

一、引言 在当今数字化时代&#xff0c;新媒体运营已成为企业和个人发展的重要手段。通过掌握一系列关键的新媒体应用&#xff0c;我们可以迅速提升运营效率&#xff0c;实现内容分发、自媒体变现等目标。本文将详细介绍新媒体运营中必须掌握的几种应用及其功能。 二、Ai新媒运…

无人机场景 - 目标检测数据集 - 夜间车辆检测数据集下载「包含VOC、COCO、YOLO三种格式」

数据集介绍&#xff1a;无人机场景夜间车辆检测数据集&#xff0c;真实场景高质量图片数据&#xff0c;涉及场景丰富&#xff0c;比如夜间无人机场景城市道路行驶车辆图片、夜间无人机场景城市道边停车车辆图片、夜间无人机场景停车场车辆图片、夜间无人机场景小区车辆图片、夜…

基于Retinex算法的图像去雾matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 (完整程序运行后无水印) 2.算法运行软件版本 matlab2022a 3.部分核心程序 &#xff08;完整版代码包含详细中文注释和操作步骤视频&#xff09…

Git本地分支更新推送到远程主分支上

本地分支&#xff08;debug&#xff09;开发之前&#xff1a; git pull origin dev&#xff08;主分支&#xff09;git merge 这步merge可能会现异常&#xff1a;error&#xff1a;Merging is not possible because you have ynmerged files&#xff0c;出现冲突文件&#xff…