做网站彩票代理多少钱啊,cn网站怎么做,魔艺极速建站,北京百度seo点击器【LetMeFly】3165.不包含相邻元素的子序列的最大和#xff1a;单点修改的线段树#xff08;动态规划#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/
给你一个整数数组 nums 和一个二维数组 q…【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] 1051 queries.length 5 * 104queries[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 leftright leftright那么这个区间就只有一个元素这个区间的 f 00 f 01 f 10 0 f00f01f100 f00f01f100 f 11 max ( 0 , n u m s [ l e f t ] ) f11\max(0, nums[left]) f11max(0,nums[left])。 否则令 m i d ⌊ l e f t r i g h t 2 ⌋ mid \lfloor\frac{leftright}{2}\rfloor mid⌊2leftright⌋递归计算 [ l e f t , m i d ] [left, mid] [left,mid]和 [ m i d 1 , r i g h t ] [mid 1, right] [mid1,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_p00f_q10, f_p01f_q00) f00max(fp00fq10,fp01fq00) f 01 max ( f p 00 f q 11 , f p 01 f q 01 ) f01 \max(f_p00f_q11, f_p01f_q01) f01max(fp00fq11,fp01fq01) f 10 max ( f p 10 f q 10 , f p 11 f q 00 ) f10 \max(f_p10f_q10, f_p11f_q00) f10max(fp10fq10,fp11fq00) f 11 max ( f p 10 f q 11 , f p 11 f q 01 ) f11 \max(f_p10f_q11, f_p11f_q01) f11max(fp10fq11,fp11fq01)
那么如何应对 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(nq\log n) O(nqlogn)其中 n l e n ( n u m s ) nlen(nums) nlen(nums) q l e n ( q u e r i e s ) qlen(queries) qlen(queries)空间复杂度 O ( n ) O(n) O(n)
AC代码
C
const unsigned int mod 1e9 7;class Solution {
private:vectorarrayunsigned 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(vectorint 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(vectorint nums, vectorvectorint queries) {tree.resize(nums.size() * 4);buildTree(nums, 0, 0, nums.size() - 1);unsigned int ans 0;for (vectorint 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和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/143452715
