2025-01-04：不包含相邻元素的子序列的最大和。用 go 语言，给定一个整数数组 nums 和一个由二维数组 queries 组成的查询列表，其中每个查询的格式为 queries[i] = [pos
作者：福大大架构师每日一题
- 2025-01-04 北京
本文字数：7316 字
阅读完需：约 24 分钟
2025-01-04：不包含相邻元素的子序列的最大和。用 go 语言，给定一个整数数组 nums 和一个由二维数组 queries 组成的查询列表，其中每个查询的格式为 queries[i] = [posi, xi]。
对于每个查询 i，首先将 nums[posi] 的值更新为 xi，然后计算在这一更新后，数组 nums 中所有不包含相邻元素的子序列的最大和。
最后，返回所有查询的结果之和。需要注意的是，由于最终答案可能非常大，因此要对其进行 1000000007 的取余处理。
请根据以上描述进行相关的处理。
1 <= nums.length <= 5 * 10000。
-100000 <= nums[i] <= 100000。
1 <= queries.length <= 5 * 10000。
queries[i] == [posi, xi]。
0 <= posi <= nums.length - 1。
-100000 <= xi <= 100000。
答案 2025-01-04：
题目来自 leetcode3165。
大体步骤如下：
1.定义了一个常量 MOD 为 1000000007，表示取余处理的数值。
2.实现了一个函数 maximumSumSubsequence，该函数接受一个整数数组 nums 以及一个查询列表 queries。首先创建一个长度为 nums 数组长度四倍的线段树 tree，然后初始化这颗线段树根据传入的 nums 数组。接着对 queries 中的每个查询进行处理：更新 nums 中指定位置的值，并计算不包含相邻元素的子序列的最大和，并将结果取余加到 ans 中。最终返回 ans。
3.定义了一个结构体 SegNode，包含四个成员变量 v00、v01、v10、v11，表示线段树中的四种情况。
4.实现了两个 SegNode 结构体的方法：Set 和 Best，分别用于设置节点的值和获取最佳值。
5.定义了一个结构体 SegTree，包含了一个整数 n 和一个指向 SegNode 结构体数组的指针 tree。
6.实现了一个 NewSegTree 函数用于创建一个 SegTree 结构体并初始化相关信息。
7.实现了 SegTree 结构体的方法：Init、Update、Query、internalInit、internalUpdate、pushup。这些方法用于初始化线段树、更新节点值、查询最佳值等功能。
8.在 main 函数中，给定了一个示例数组 nums 和查询 queries，然后调用 maximumSumSubsequence 函数计算不包含相邻元素的子序列的最大和，并打印结果。
总的时间复杂度：
初始化线段树的时间复杂度为 O(n)。
每次查询的时间复杂度为 O(logn)。
因此，总的时间复杂度为 O(n + q*logn)，其中 n 为数组长度，q 为查询次数。
总的额外空间复杂度：
线段树的空间复杂度为 O(n)。
因此，总的额外空间复杂度为 O(n)，其中 n 为数组长度。
Go 完整代码如下：
package main
import ( "fmt" "math")
const MOD = 1000000007
func maximumSumSubsequence(nums []int, queries [][]int) int { n := len(nums) tree := NewSegTree(n) tree.Init(nums)
ans := int64(0) for _, q := range queries { tree.Update(q[0], q[1]) ans = (ans + tree.Query()) % MOD } return int(ans)}
type SegNode struct { v00, v01, v10, v11 int64}
func NewSegNode() *SegNode { return &SegNode{0, 0, 0, 0}}
func (sn *SegNode) Set(v int64) { sn.v00, sn.v01, sn.v10 = 0, 0, 0 sn.v11 = int64(math.Max(float64(v), 0))}
func (sn *SegNode) Best() int64 { return sn.v11}
type SegTree struct { n int tree []*SegNode}
func NewSegTree(n int) *SegTree { tree := make([]*SegNode, n * 4 + 1) for i := range tree { tree[i] = NewSegNode() } return &SegTree{n, tree}}
func (st *SegTree) Init(nums []int) { st.internalInit(nums, 1, 1, st.n)}
func (st *SegTree) Update(x, v int) { st.internalUpdate(1, 1, st.n, x + 1, int64(v))}
func (st *SegTree) Query() int64 { return st.tree[1].Best()}
func (st *SegTree) internalInit(nums []int, x, l, r int) { if l == r { st.tree[x].Set(int64(nums[l - 1])) return } mid := (l + r) / 2 st.internalInit(nums, x * 2, l, mid) st.internalInit(nums, x * 2 + 1, mid + 1, r) st.pushup(x)}
func (st *SegTree) internalUpdate(x, l, r int, pos int, v int64) { if l > pos || r < pos { return } if l == r { st.tree[x].Set(v) return } mid := (l + r) / 2 st.internalUpdate(x * 2, l, mid, pos, v) st.internalUpdate(x * 2 + 1, mid + 1, r, pos, v) st.pushup(x)}
func (st *SegTree) pushup(x int) { l, r := x * 2, x * 2 + 1 st.tree[x].v00 = max(st.tree[l].v00 + st.tree[r].v10, st.tree[l].v01 + st.tree[r].v00) st.tree[x].v01 = max(st.tree[l].v00 + st.tree[r].v11, st.tree[l].v01 + st.tree[r].v01) st.tree[x].v10 = max(st.tree[l].v10 + st.tree[r].v10, st.tree[l].v11 + st.tree[r].v00) st.tree[x].v11 = max(st.tree[l].v10 + st.tree[r].v11, st.tree[l].v11 + st.tree[r].v01)}
func main() { nums := []int{3,5,9} queries := [][]int{{1,-2},{0,-3}} result := maximumSumSubsequence(nums, queries) fmt.Println(result)}
复制代码
Rust 完整代码如下：
use std::cmp::max;
const MOD: i64 = 1_000_000_007;
#[derive(Clone)]struct SegNode { v00: i64, v01: i64, v10: i64, v11: i64,}
impl SegNode { fn new() -> Self { SegNode { v00: 0, v01: 0, v10: 0, v11: 0, } }
fn set(&mut self, v: i64) { self.v00 = 0; self.v01 = 0; self.v10 = 0; self.v11 = max(v, 0); }
fn best(&self) -> i64 { self.v11 }}
struct SegTree { n: usize, tree: Vec<SegNode>,}
impl SegTree { fn new(n: usize) -> Self { let tree = vec![SegNode::new(); n * 4]; SegTree { n, tree } }
fn init(&mut self, nums: &[i32]) { self.internal_init(nums, 1, 1, self.n); }
fn update(&mut self, pos: usize, v: i32) { self.internal_update(1, 1, self.n, pos + 1, v as i64); }
fn query(&self) -> i64 { self.tree[1].best() }
fn internal_init(&mut self, nums: &[i32], x: usize, l: usize, r: usize) { if l == r { self.tree[x].set(nums[l - 1] as i64); return; } let mid = (l + r) / 2; self.internal_init(nums, x * 2, l, mid); self.internal_init(nums, x * 2 + 1, mid + 1, r); self.push_up(x); }
fn internal_update(&mut self, x: usize, l: usize, r: usize, pos: usize, v: i64) { if l > pos || r < pos { return; } if l == r { self.tree[x].set(v); return; } let mid = (l + r) / 2; self.internal_update(x * 2, l, mid, pos, v); self.internal_update(x * 2 + 1, mid + 1, r, pos, v); self.push_up(x); }
fn push_up(&mut self, x: usize) { let l = x * 2; let r = x * 2 + 1; self.tree[x].v00 = max( self.tree[l].v00 + self.tree[r].v10, self.tree[l].v01 + self.tree[r].v00, ); self.tree[x].v01 = max( self.tree[l].v00 + self.tree[r].v11, self.tree[l].v01 + self.tree[r].v01, ); self.tree[x].v10 = max( self.tree[l].v10 + self.tree[r].v10, self.tree[l].v11 + self.tree[r].v00, ); self.tree[x].v11 = max( self.tree[l].v10 + self.tree[r].v11, self.tree[l].v11 + self.tree[r].v01, ); }}
fn maximum_sum_subsequence(nums: &[i32], queries: &[(usize, i32)]) -> i64 { let n = nums.len(); let mut tree = SegTree::new(n); tree.init(nums); let mut ans = 0;
for (x, v) in queries { tree.update(*x, *v); ans = (ans + tree.query()) % MOD; }
ans}
fn main() { let nums = vec![3, 5, 9]; let queries = vec![(1, -2), (0, -3)]; let result = maximum_sum_subsequence(&nums, &queries); println!("{}", result);}
复制代码
C 完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <math.h>
#define MOD 1000000007
typedef struct { long long v00, v01, v10, v11;} SegNode;
typedef struct { int n; SegNode* tree;} SegTree;
SegNode newSegNode() { SegNode node; node.v00 = 0; node.v01 = 0; node.v10 = 0; node.v11 = 0; return node;}
void setSegNode(SegNode* sn, long long v) { sn->v00 = 0; sn->v01 = 0; sn->v10 = 0; sn->v11 = fmax(v, 0);}
long long bestSegNode(SegNode* sn) { return sn->v11;}
SegTree* newSegTree(int n) { SegTree* tree = (SegTree*)malloc(sizeof(SegTree)); tree->n = n; tree->tree = (SegNode*)malloc(sizeof(SegNode) * (4 * n + 1));
for (int i = 0; i < 4 * n + 1; i++) { tree->tree[i] = newSegNode(); }
return tree;}
void pushup(SegTree* st, int x);
void internalInit(SegTree* st, int* nums, int x, int l, int r) { if (l == r) { setSegNode(&st->tree[x], (long long)nums[l - 1]); return; } int mid = (l + r) / 2; internalInit(st, nums, x * 2, l, mid); internalInit(st, nums, x * 2 + 1, mid + 1, r); pushup(st, x);}
void pushup(SegTree* st, int x) { int l = x * 2; int r = x * 2 + 1; st->tree[x].v00 = fmax(st->tree[l].v00 + st->tree[r].v10, st->tree[l].v01 + st->tree[r].v00); st->tree[x].v01 = fmax(st->tree[l].v00 + st->tree[r].v11, st->tree[l].v01 + st->tree[r].v01); st->tree[x].v10 = fmax(st->tree[l].v10 + st->tree[r].v10, st->tree[l].v11 + st->tree[r].v00); st->tree[x].v11 = fmax(st->tree[l].v10 + st->tree[r].v11, st->tree[l].v11 + st->tree[r].v01);}
void internalUpdate(SegTree* st, int x, int l, int r, int pos, long long v) { if (l > pos || r < pos) { return; } if (l == r) { setSegNode(&st->tree[x], v); return; } int mid = (l + r) / 2; internalUpdate(st, x * 2, l, mid, pos, v); internalUpdate(st, x * 2 + 1, mid + 1, r, pos, v); pushup(st, x);}
long long query(SegTree* st) { return bestSegNode(&st->tree[1]);}
void initSegTree(SegTree* st, int* nums) { internalInit(st, nums, 1, 1, st->n);}
void updateSegTree(SegTree* st, int pos, int v) { internalUpdate(st, 1, 1, st->n, pos + 1, v);}
long long maximumSumSubsequence(int* nums, int numsSize, int(*queries)[2], int queriesSize) { SegTree* tree = newSegTree(numsSize); initSegTree(tree, nums); long long ans = 0;
for (int i = 0; i < queriesSize; i++) { updateSegTree(tree, queries[i][0], queries[i][1]); ans = (ans + query(tree)) % MOD; }
// Free allocated memory free(tree->tree); free(tree); return ans;}
int main() { int nums[] = { 3, 5, 9 }; int queries[2][2] = { {1, -2}, {0, -3} }; long long result = maximumSumSubsequence(nums, 3, queries, 2); printf("%lld\n", result); return 0;}
复制代码
C++完整代码如下：
#include <iostream>#include <vector>#include <algorithm>#include <cmath>
const int MOD = 1000000007;
class SegNode {public: long long v00, v01, v10, v11;
SegNode() : v00(0), v01(0), v10(0), v11(0) {}
void set(long long v) { v00 = 0; v01 = 0; v10 = 0; v11 = std::max(v, 0LL); }
long long best() const { return v11; }};
class SegTree {private: int n; std::vector<SegNode> tree;
void pushup(int x) { int l = x * 2; int r = x * 2 + 1; tree[x].v00 = std::max(tree[l].v00 + tree[r].v10, tree[l].v01 + tree[r].v00); tree[x].v01 = std::max(tree[l].v00 + tree[r].v11, tree[l].v01 + tree[r].v01); tree[x].v10 = std::max(tree[l].v10 + tree[r].v10, tree[l].v11 + tree[r].v00); tree[x].v11 = std::max(tree[l].v10 + tree[r].v11, tree[l].v11 + tree[r].v01); }
void internalInit(const std::vector<int>& nums, int x, int l, int r) { if (l == r) { tree[x].set(static_cast<long long>(nums[l - 1])); return; } int mid = (l + r) / 2; internalInit(nums, x * 2, l, mid); internalInit(nums, x * 2 + 1, mid + 1, r); pushup(x); }
void internalUpdate(int x, int l, int r, int pos, long long v) { if (l > pos || r < pos) { return; } if (l == r) { tree[x].set(v); return; } int mid = (l + r) / 2; internalUpdate(x * 2, l, mid, pos, v); internalUpdate(x * 2 + 1, mid + 1, r, pos, v); pushup(x); }
public: SegTree(int n) : n(n) { tree.resize(n * 4); }
void init(const std::vector<int>& nums) { internalInit(nums, 1, 1, n); }
void update(int pos, int v) { internalUpdate(1, 1, n, pos + 1, static_cast<long long>(v)); }
long long query() const { return tree[1].best(); }};
long long maximumSumSubsequence(const std::vector<int>& nums, const std::vector<std::pair<int, int>>& queries) { int n = nums.size(); SegTree tree(n); tree.init(nums); long long ans = 0;
for (const auto& query : queries) { tree.update(query.first, query.second); ans = (ans + tree.query()) % MOD; }
return ans;}
int main() { std::vector<int> nums = { 3, 5, 9 }; std::vector<std::pair<int, int>> queries = { {1, -2}, {0, -3} }; long long result = maximumSumSubsequence(nums, queries); std::cout << result << std::endl; return 0;}
复制代码
Python 完整代码如下：
# -*-coding:utf-8-*-
class SegNode: def __init__(self): self.v00 = 0 self.v01 = 0 self.v10 = 0 self.v11 = 0
def set(self, v): self.v00 = 0 self.v01 = 0 self.v10 = 0 self.v11 = max(v, 0)
def best(self): return self.v11
class SegTree: def __init__(self, n): self.n = n self.tree = [SegNode() for _ in range(n * 4 + 1)]
def init(self, nums): self._internal_init(nums, 1, 1, self.n)
def update(self, x, v): self._internal_update(1, 1, self.n, x + 1, v)
def query(self): return self.tree[1].best()
def _internal_init(self, nums, x, l, r): if l == r: self.tree[x].set(nums[l - 1]) return mid = (l + r) // 2 self._internal_init(nums, x * 2, l, mid) self._internal_init(nums, x * 2 + 1, mid + 1, r) self._pushup(x)
def _internal_update(self, x, l, r, pos, v): if l > pos or r < pos: return if l == r: self.tree[x].set(v) return mid = (l + r) // 2 self._internal_update(x * 2, l, mid, pos, v) self._internal_update(x * 2 + 1, mid + 1, r, pos, v) self._pushup(x)
def _pushup(self, x): l, r = x * 2, x * 2 + 1 self.tree[x].v00 = max(self.tree[l].v00 + self.tree[r].v10, self.tree[l].v01 + self.tree[r].v00) self.tree[x].v01 = max(self.tree[l].v00 + self.tree[r].v11, self.tree[l].v01 + self.tree[r].v01) self.tree[x].v10 = max(self.tree[l].v10 + self.tree[r].v10, self.tree[l].v11 + self.tree[r].v00) self.tree[x].v11 = max(self.tree[l].v10 + self.tree[r].v11, self.tree[l].v11 + self.tree[r].v01)
MOD = 1000000007
def maximum_sum_subsequence(nums, queries): n = len(nums) tree = SegTree(n) tree.init(nums)
ans = 0 for q in queries: tree.update(q[0], q[1]) ans = (ans + tree.query()) % MOD return ans
if __name__ == "__main__": nums = [3, 5, 9] queries = [[1, -2], [0, -3]] result = maximum_sum_subsequence(nums, queries) print(result)
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/0973d6b9939ed31af996518ab】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
![2025-01-04：不包含相邻元素的子序列的最大和。用go语言，给定一个整数数组 nums 和一个由二维数组 queries 组成的查询列表，其中每个查询的格式为 queries[i] = [pos_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论