2025-01-04：不包含相邻元素的子序列的最大和。用go语言，给定一个整数数组 nums 和一个由二维数组 queries

福大大架构师每日一题

发布于 2025-01-07 08:23:25

11800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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：

chatgpt[1]

题目来自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
}
returnint(ans)
}

typeSegNodestruct{
    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
}

typeSegTreestruct{
    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)]
structSegNode{
    v00:i64,
    v01:i64,
    v10:i64,
    v11:i64,
}

implSegNode{
fnnew()->Self{
SegNode{
            v00:0,
            v01:0,
            v10:0,
            v11:0,
}
}

fnset(&mutself, v:i64){
self.v00 =0;
self.v01 =0;
self.v10 =0;
self.v11 =max(v,0);
}

fnbest(&self)->i64{
self.v11
}
}

structSegTree{
    n:usize,
    tree:Vec<SegNode>,
}

implSegTree{
fnnew(n:usize)->Self{
lettree=vec![SegNode::new(); n *4];
SegTree{ n, tree }
}

fninit(&mutself, nums:&[i32]){
self.internal_init(nums,1,1,self.n);
}

fnupdate(&mutself, pos:usize, v:i32){
self.internal_update(1,1,self.n, pos +1, v asi64);
}

fnquery(&self)->i64{
self.tree[1].best()
}

fninternal_init(&mutself, nums:&[i32], x:usize, l:usize, r:usize){
if l == r {
self.tree[x].set(nums[l -1]asi64);
return;
}
letmid=(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);
}

fninternal_update(&mutself, 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;
}
letmid=(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);
}

fnpush_up(&mutself, x:usize){
letl= x *2;
letr= 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,
);
}
}

fnmaximum_sum_subsequence(nums:&[i32], queries:&[(usize,i32)])->i64{
letn= nums.len();
letmut tree=SegTree::new(n);
    tree.init(nums);
letmut ans=0;

for(x, v)in queries {
        tree.update(*x,*v);
        ans =(ans + tree.query())% MOD;
}

    ans
}

fnmain(){
letnums=vec![3,5,9];
letqueries=vec![(1,-2),(0,-3)];
letresult=maximum_sum_subsequence(&nums,&queries);
println!("{}", result);
}

C完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MOD 1000000007

typedefstruct {
longlong v00, v01, v10, v11;
}SegNode;

typedefstruct {
int n;
SegNode* tree;
}SegTree;

SegNodenewSegNode(){
SegNode node;
    node.v00 =0;
    node.v01 =0;
    node.v10 =0;
    node.v11 =0;
return node;
}

voidsetSegNode(SegNode* sn, long long v){
    sn->v00 =0;
    sn->v01 =0;
    sn->v10 =0;
    sn->v11 = fmax(v,0);
}

longlongbestSegNode(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;
}

voidpushup(SegTree* st, int x);

voidinternalInit(SegTree* st, int* nums, int x, int l, int r){
if(l == r){
        setSegNode(&st->tree[x],(longlong)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);
}

voidpushup(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);
}

voidinternalUpdate(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);
}

longlongquery(SegTree* st){
return bestSegNode(&st->tree[1]);
}

voidinitSegTree(SegTree* st, int* nums){
    internalInit(st, nums,1,1, st->n);
}

voidupdateSegTree(SegTree* st, int pos, int v){
    internalUpdate(st,1,1, st->n, pos +1, v);
}

longlongmaximumSumSubsequence(int* nums, int numsSize, int(*queries)[2], int queriesSize){
SegTree* tree = newSegTree(numsSize);
    initSegTree(tree, nums);
longlong 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;
}

intmain(){
int nums[]={3,5,9};
int queries[2][2]={{1,-2},{0,-3}};
longlong result = maximumSumSubsequence(nums,3, queries,2);
printf("%lld\n", result);
return0;
}

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

constint MOD =1000000007;

classSegNode{
public:
longlong 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;
}
};

classSegTree{
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<longlong>(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<longlong>(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);
longlong ans =0;

for(constauto& 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}};
longlong result =maximumSumSubsequence(nums, queries);
    std::cout << result << std::endl;
return0;
}

Python完整代码如下：

# -*-coding:utf-8-*-

classSegNode:
def__init__(self):
        self.v00 =0
        self.v01 =0
        self.v10 =0
        self.v11 =0

defset(self, v):
        self.v00 =0
        self.v01 =0
        self.v10 =0
        self.v11 =max(v,0)

defbest(self):
return self.v11


classSegTree:
def__init__(self, n):
        self.n = n
        self.tree =[SegNode()for _ inrange(n *4+1)]

definit(self, nums):
        self._internal_init(nums,1,1, self.n)

defupdate(self, x, v):
        self._internal_update(1,1, self.n, x +1, v)

defquery(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

defmaximum_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)