当前位置: 首页 > news >正文

LeetCode每日一题3165---不包含相邻元素的子序列的最大和

一、题目描述

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

二、解题思路
要解决这个问题,我们可以使用动态规划来计算不包含相邻元素的子序列的最大和。在处理每个查询时,我们需要更新数组 nums 并重新计算最大和。以下是解决此问题的基本步骤和思路:

定义动态规划状态:
我们定义 dp[i] 为考虑前 i 个元素时,不包含相邻元素的子序列的最大和。
状态转移方程为:
dp[i]=max(dp[i−1],dp[i−2]+nums[i])
这里 dp[i-1] 是不选择当前元素 nums[i] 的最大和,而 dp[i-2] + nums[i] 是选择当前元素后的最大和。
2. 初始化状态:

  • dp[0] = \max(0, nums[0]) (如果第一个元素是负数,选择空子序列)
  • dp[1] = \max(dp[0], nums[1]) (第一或第二个元素)

计算数组的初始值:

在处理所有查询之前,首先计算给定 nums 的初始状态。
处理查询:

对于每个查询,将特定位置的值更新到新的值,然后重新计算 dp。

三、代码


class Solution {int mod=(int)1e9+7;public int maximumSumSubsequence(int[] nums, int[][] queries) {SegTree st=new SegTree(0,nums.length-1);build(st,nums);long ans=0;for(int q[]:queries){update(st,q[0],q[1]);ans+=Math.max(Math.max(st.sum0,st.sum1),Math.max(st.sum2,st.sum3));}return (int)(ans%mod);}void update(SegTree st,int idx,int val){int l=st.l,r=st.r;if(l==r){st.sum0=st.sum1=st.sum2=0;st.sum3=val;}else{update(idx<=((l+r)>>1)?st.left:st.right,idx,val);clear(st);}}void build(SegTree st,int a[]){int l=st.l,r=st.r;if(l==r){st.sum0=st.sum1=st.sum2=0;st.sum3=a[l];}else{int mid=(l+r)>>1;st.left=new SegTree(l,mid);st.right=new SegTree(mid+1,r);build(st.left,a);build(st.right,a);clear(st);}}void clear(SegTree st){//用子树更新自己的数据SegTree left=st.left,right=st.right;st.sum0=Math.max(left.sum1+right.sum0,left.sum0+right.sum2);st.sum1=Math.max(left.sum0+right.sum3,left.sum1+right.sum1);st.sum2=Math.max(left.sum2+right.sum2,left.sum3+right.sum0);st.sum3=Math.max(left.sum3+right.sum1,left.sum2+right.sum3);}
}
class SegTree{SegTree left,right;int l,r;long sum0,sum1,sum2,sum3;public SegTree(int l,int r){this.l=l;this.r=r;}
}

http://www.mrgr.cn/news/62483.html

相关文章:

  • 如何使用AdsPower指纹浏览器克服爬虫技术限制,安全高效进行爬虫!
  • 火山引擎VeDI数据服务平台:在电商场景中,如何解决API编排问题?
  • TypeScript(中)+算法(二)
  • Spring 设计模式之装饰器模式
  • 【热门主题】000018 人工智能深度学习模型:探索与应用
  • Vue-$el属性
  • Springboot3.3 + Mybatis / Mybatis-plus
  • Python虚拟显示器pyvirtualdisplay
  • 这个AI植物整活创意项目,操作起来没难度!
  • 特斯联巨亏数十亿:毛利率剧烈波动下滑,高管动荡引发关注
  • [vulnhub] SecTalks:BNE0x00 - Minotaur
  • 安信金控:K金,金店回收吗?
  • 【软件系统计划书】项目计划书,项目总体计划,实施计划,运维计划书(word原件)
  • 【JAVA毕业设计】基于Vue和SpringBoot的在线文档管理系统
  • 预览 PDF 文档
  • 基于QT(C++)实现(界面)即时通讯软件
  • 语义检索系统嵌入模型选型技术方案
  • 海思MPP音视频总结
  • 【综合算法学习】(第十二篇)
  • LC946. 验证栈序列
  • 引导徒弟找到用java程序拉取钉钉考勤记录的方法
  • 最新EI会议论文投稿指南:10个热门学术会议推荐
  • Chrome浏览器音/视频无法自动播放
  • OpenCV自动滑块验证(Java版)
  • Spring Boot助力校园社团信息数字化管理
  • Python爬虫:在1688上“侦探游戏”获取店铺详情