当前位置：首页 > article >正文

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

article 2024/11/1 22:31:55

一、题目描述

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