题目：
给你一个整数数组 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] <= 1051 <= queries.length <= 5 * 104queries[i] == [posi, xi]0 <= posi <= nums.length - 1-105 <= xi <= 105
思路：
暴力枚举每个 query，对于每个 query[i]，改变 nums 后，通过动态规划求出不具有相邻元素的最大子序列和。(这个算法会超时)
动态规划算法：
dp[i] 是以 nums[i] 为结尾的满足要求的最大子序列和，对于 0 < j < i - 1 的所有 j，
dp[i] = max(dp[i], dp[j] + nums[i]) dp[j] > 0
dp[i] = max(dp[i], nums[i]) dp[j] <= 0
所以，dp[i] 最开始是 INT_MIN。dp[0] = nums[0], dp[1] = nums[1];
代码：
class Solution {
public:
int getMaxSequence(vector<int>& nums) {
int n = nums.size();
if (n == 1) return max(0, nums[0]);
int res = 0;
vector<int> dp(n, INT_MIN);
dp[0] = nums[0];dp[1] = nums[1];
res = max(res, dp[0]);
res = max(res, dp[1]);
for (int i = 2; i < n; i++) {
for (int j = i - 2; j >= 0; j--) {
if (dp[j] > 0) dp[i] = max(dp[i], nums[i] + dp[j]);
else dp[i] = max(dp[i], nums[i]);
}
res = max(res, dp[i]);
}
return res;
}
int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
// 动态规划 + 暴力枚举
int ans = 0;
int mod = 1e9 + 7;
for (int i = 0; i < queries.size(); i++) {
int pos = queries[i][0], x = queries[i][1];
nums[pos] = x;
ans = (ans + getMaxSequence(nums)) % mod;
}
return ans;
}
};