3165. 非相邻元素子序列的最大和

Hard

题目描述

给你一个由整数组成的数组 nums。另外给你一个二维数组 queries，其中 queries[i] = [posi, xi]。

对于查询 i，我们首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，即 nums 的一个子序列的最大和，其中不能选择任何两个相邻的元素。

返回所有查询答案的和。

由于最终答案可能很大，请返回它对 10^9 + 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 * 10^4
-10^5 <= nums[i] <= 10^5
1 <= queries.length <= 5 * 10^4
queries[i] == [posi, xi]
0 <= posi <= nums.length - 1
-10^5 <= xi <= 10^5

解题思路

这是一个经典的"打家劫舍"问题的变种，需要在每次修改后快速计算非相邻元素的最大和。

基本思路：最直观的方法是每次查询后用动态规划重新计算整个数组，时间复杂度为 O(queries × n)。

优化思路：使用线段树优化。关键观察是：对于任意区间，我们需要维护四种状态：

dp[0][0]：左端点不选，右端点不选的最大和
dp[0][1]：左端点不选，右端点选的最大和
dp[1][0]：左端点选，右端点不选的最大和
dp[1][1]：左端点选，右端点选的最大和

合并两个子区间时，需要考虑相邻约束：左区间的右端点和右区间的左端点不能同时选择。

线段树的每个节点存储这四个状态值，单点更新时间复杂度为 O(log n)，总时间复杂度降为 O(queries × log n)。

实现要点：

线段树节点存储四种状态的最大值
合并操作考虑相邻约束
处理负数情况，可以选择不选任何元素（和为0）

代码实现

class Solution {
private:
    const int MOD = 1e9 + 7;
    
    struct Node {
        long long dp[2][2];
        Node() {
            dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
        }
    };
    
    vector<Node> tree;
    int n;
    
    void build(vector<int>& nums, int v, int l, int r) {
        if (l == r) {
            tree[v].dp[0][0] = 0;
            tree[v].dp[0][1] = max(0, nums[l]);
            tree[v].dp[1][0] = 0;
            tree[v].dp[1][1] = max(0, nums[l]);
        } else {
            int mid = (l + r) / 2;
            build(nums, 2*v, l, mid);
            build(nums, 2*v+1, mid+1, r);
            merge(v);
        }
    }
    
    void merge(int v) {
        int left = 2*v, right = 2*v+1;
        tree[v].dp[0][0] = max({tree[left].dp[0][0] + tree[right].dp[0][0],
                                tree[left].dp[0][0] + tree[right].dp[1][0],
                                tree[left].dp[0][1] + tree[right].dp[0][0]});
        tree[v].dp[0][1] = max({tree[left].dp[0][0] + tree[right].dp[0][1],
                                tree[left].dp[0][0] + tree[right].dp[1][1],
                                tree[left].dp[0][1] + tree[right].dp[0][1]});
        tree[v].dp[1][0] = max({tree[left].dp[1][0] + tree[right].dp[0][0],
                                tree[left].dp[1][0] + tree[right].dp[1][0],
                                tree[left].dp[1][1] + tree[right].dp[0][0]});
        tree[v].dp[1][1] = max({tree[left].dp[1][0] + tree[right].dp[0][1],
                                tree[left].dp[1][0] + tree[right].dp[1][1],
                                tree[left].dp[1][1] + tree[right].dp[0][1]});
    }
    
    void update(int v, int l, int r, int pos, int val) {
        if (l == r) {
            tree[v].dp[0][0] = 0;
            tree[v].dp[0][1] = max(0, val);
            tree[v].dp[1][0] = 0;
            tree[v].dp[1][1] = max(0, val);
        } else {
            int mid = (l + r) / 2;
            if (pos <= mid) {
                update(2*v, l, mid, pos, val);
            } else {
                update(2*v+1, mid+1, r, pos, val);
            }
            merge(v);
        }
    }
    
public:
    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        n = nums.size();
        tree.resize(4 * n);
        build(nums, 1, 0, n-1);
        
        long long ans = 0;
        for (auto& query : queries) {
            update(1, 0, n-1, query[0], query[1]);
            ans = (ans + max({tree[1].dp[0][0], tree[1].dp[0][1], 
                             tree[1].dp[1][0], tree[1].dp[1][1]})) % MOD;
        }
        return ans;
    }
};

class Solution:
    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # 线段树节点，存储四种状态
        tree = [[[0, 0], [0, 0]] for _ in range(4 * n)]
        
        def merge(v):
            left, right = 2*v, 2*v+1
            # dp[i][j] 表示左端点选择状态i，右端点选择状态j的最大和
            tree[v][0][0] = max(tree[left][0][0] + tree[right][0][0],
                               tree[left][0][0] + tree[right][1][0],
                               tree[left][0][1] + tree[right][0][0])
            tree[v][0][1] = max(tree[left][0][0] + tree[right][0][1],
                               tree[left][0][0] + tree[right][1][1],
                               tree[left][0][1] + tree[right][0][1])
            tree[v][1][0] = max(tree[left][1][0] + tree[right][0][0],
                               tree[left][1][0] + tree[right][1][0],
                               tree[left][1][1] + tree[right][0][0])
            tree[v][1][1] = max(tree[left][1][0] + tree[right][0][1],
                               tree[left][1][0] + tree[right][1][1],
                               tree[left][1][1] + tree[right][0][1])
        
        def build(v, l, r):
            if l == r:
                tree[v][0][0] = 0
                tree[v][0][1] = max(0, nums[l])
                tree[v][1][0] = 0
                tree[v][1][1] = max(0, nums[l])
            else:
                mid = (l + r) // 2
                build(2*v, l, mid)
                build(2*v+1, mid+1, r)
                merge(v)
        
        def update(v, l, r, pos, val):
            if l == r:
                tree[v][0][0] = 0
                tree[v][0][1] = max(0, val)
                tree[v][1][0] = 0
                tree[v][1][1] = max(0, val)
            else:
                mid = (l + r) // 2
                if pos <= mid:
                    update(2*v, l, mid, pos, val)
                else:
                    update(2*v+1, mid+1, r, pos, val)
                merge(v)
        
        build(1, 0, n-1)
        ans = 0
        
        for pos, val in queries:
            update(1, 0, n-1, pos, val)
            ans = (ans + max(tree[1][0][0], tree[1][0][1], 
                           tree[1][1][0], tree[1][1][1])) % MOD
        
        return ans

public class Solution {
    private const int MOD = 1000000007;
    
    private class Node {
        public long[,] dp = new long[2, 2];
        public Node() {
            dp[0,0] = dp[0,1] = dp[1,0] = dp[1,1] = 0;
        }
    }
    
    private Node[] tree;
    private int n;
    
    private void Build(int[] nums, int v, int l, int r) {
        if (l == r) {
            tree[v].dp[0,0] = 0;
            tree[v].dp[0,1] = Math.Max(0, nums[l]);
            tree[v].dp[1,0] = 0;
            tree[v].dp[1,1] = Math.Max(0, nums[l]);
        } else {
            int mid = (l + r) / 2;
            Build(nums, 2*v, l, mid);
            Build(nums, 2*v+1, mid+1, r);
            Merge(v);
        }
    }
    
    private void Merge(int v) {
        int left = 2*v, right = 2*v+1;
        tree[v].dp[0,0] = Math.Max(Math.Max(tree[left].dp[0,0] + tree[right].dp[0,0],
                                          tree[left].dp[0,0] + tree[right].dp[1,0]),
                                          tree[left].dp[0,1] + tree[right].dp[0,0]);
        tree[v].dp[0,1] = Math.Max(Math.Max(tree[left].dp[0,0] + tree[right].dp[0,1],
                                          tree[left].dp[0,0] + tree[right].dp[1,1]),
                                          tree[left].dp[0,1] + tree[right].dp[0,1]);
        tree[v].dp[1,0] = Math.Max(Math.Max(tree[left].dp[1,0] + tree[right].dp[0,0],
                                          tree[left].dp[1,0] + tree[right].dp[1,0]),
                                          tree[left].dp[1,1] + tree[right].dp[0,0]);
        tree[v].dp[1,1] = Math.Max(Math.Max(tree[left].dp[1,0] + tree[right].dp[0,1],
                                          tree[left].dp[1,0] + tree[right].dp[1,1]),
                                          tree[left].dp[1,1] + tree[right].dp[0,1]);
    }
    
    private void Update(int v, int l, int r, int pos, int val) {
        if (l == r) {
            tree[v].dp[0,0] = 0;
            tree[v].dp[0,1] = Math.Max(0, val);
            tree[v].dp[1,0] = 0;
            tree[v].dp[1,1] = Math.Max(0, val);
        } else {
            int mid = (l + r) / 2;
            if (pos <= mid) {
                Update(2*v, l, mid, pos, val);
            } else {
                Update(2*v+1, mid+1, r, pos, val);
            }
            Merge(v);
        }
    }
    
    public int MaximumSumSubsequence(int[] nums, int[][] queries) {
        n = nums.Length;
        tree = new Node[4 * n];
        for (int i = 0; i < tree.Length; i++) {
            tree[i] = new Node();
        }
        
        Build(nums, 1, 0, n-1);
        
        long ans = 0;
        foreach (var query in queries) {
            Update(1, 0, n-1, query[0], query[1]);
            ans = (ans + Math.Max(Math.Max(tree[1].dp[0,0], tree[1].dp[0,1]), 
                                 Math.Max(tree[1].dp[1,0], tree[1].dp[1,1]))) % MOD;
        }
        return (int)ans;
    }
}

var maximumSumSubsequence = function(nums, queries) {
    const MOD = 1000000007;
    const n = nums.length;
    
    class SegmentTree {
        constructor(arr) {
            this.n = arr.length;
            this.tree = new Array(4 * this.n);
            this.build(arr, 0, 0, this.n - 1);
        }
        
        build(arr, v, tl, tr) {
            if (tl === tr) {
                this.tree[v] = this.calcNode(arr[tl]);
            } else {
                const tm = Math.floor((tl + tr) / 2);
                this.build(arr, 2 * v + 1, tl, tm);
                this.build(arr, 2 * v + 2, tm + 1, tr);
                this.tree[v] = this.merge(this.tree[2 * v + 1], this.tree[2 * v + 2]);
            }
        }
        
        calcNode(val) {
            return {
                take_take: val,
                take_skip: val,
                skip_take: 0,
                skip_skip: 0
            };
        }
        
        merge(left, right) {
            return {
                take_take: Math.max(left.take_skip + right.skip_take, left.take_skip + right.take_take),
                take_skip: Math.max(left.take_take, left.take_skip),
                skip_take: Math.max(left.skip_skip + right.skip_take, left.skip_skip + right.take_take),
                skip_skip: Math.max(left.skip_take, left.skip_skip)
            };
        }
        
        update(pos, val) {
            this.updateHelper(0, 0, this.n - 1, pos, val);
        }
        
        updateHelper(v, tl, tr, pos, val) {
            if (tl === tr) {
                this.tree[v] = this.calcNode(val);
            } else {
                const tm = Math.floor((tl + tr) / 2);
                if (pos <= tm) {
                    this.updateHelper(2 * v + 1, tl, tm, pos, val);
                } else {
                    this.updateHelper(2 * v + 2, tm + 1, tr, pos, val);
                }
                this.tree[v] = this.merge(this.tree[2 * v + 1], this.tree[2 * v + 2]);
            }
        }
        
        query() {
            return Math.max(
                Math.max(this.tree[0].take_take, this.tree[0].take_skip),
                Math.max(this.tree[0].skip_take, this.tree[0].skip_skip)
            );
        }
    }
    
    const st = new SegmentTree(nums);
    let result = 0;
    
    for (const [pos, val] of queries) {
        st.update(pos, val);
        result = (result + Math.max(0, st.query())) % MOD;
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析