maximum-sum-of-subsequence-with-non-adjacent-elements

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>nums</code> consisting of integers. You are also given a 2D array <code>queries</code>, where <code>queries[i] = [posi, xi]</code>.

For query <code>i</code>, we first set <code>nums[posi]</code> equal to <code>xi</code>, then we calculate the answer to query <code>i</code> which is the maximum sum of a subsequence of <code>nums</code> where no two adjacent elements are selected.

Return the sum of the answers to all queries.

Since the final answer may be very large, return it modulo <code>109 + 7</code>.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [3,5,9], queries = [[1,-2],[0,-3]]

Output: 21

Explanation: 
After the 1st query, <code>nums = [3,-2,9]</code> and the maximum sum of a subsequence with non-adjacent elements is <code>3 + 9 = 12</code>. 
After the 2nd query, <code>nums = [-3,-2,9]</code> and the maximum sum of a subsequence with non-adjacent elements is 9.
</div>

Example 2:

<div class="example-block">
Input: nums = [0,-1], queries = [[0,-5]]

Output: 0

Explanation: 
After the 1st query, <code>nums = [-5,-1]</code> and the maximum sum of a subsequence with non-adjacent elements is 0 (choosing an empty subsequence).
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 104</code></li>
	<li><code>-105 &lt;= nums[i] &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 5 * 104</code></li>
	<li><code>queries[i] == [posi, xi]</code></li>
	<li><code>0 &lt;= posi &lt;= nums.length - 1</code></li>
	<li><code>-105 &lt;= xi &lt;= 105</code></li>
</ul>

maximumSumSubsequence

Maximum Sum of Subsequence With Non-adjacent Elements

Segment Tree

Array

Divide and Conquer

Dynamic Programming

给你一个整数数组 <code>nums</code> 和一个二维数组 <code>queries</code>，其中 <code>queries[i] = [posi, xi]</code>。

对于每个查询 <code>i</code>，首先将 <code>nums[posi]</code> 设置为 <code>xi</code>，然后计算查询 <code>i</code> 的答案，该答案为 <code>nums</code> 中 不包含相邻元素 的 子序列 的 最大 和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 <code>109 + 7</code> 取余 的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [3,5,9], queries = [[1,-2],[0,-3]]

输出：21

解释： 
执行第 1 个查询后，<code>nums = [3,-2,9]</code>，不包含相邻元素的子序列的最大和为 <code>3 + 9 = 12</code>。 
执行第 2 个查询后，<code>nums = [-3,-2,9]</code>，不包含相邻元素的子序列的最大和为 9 。
</div>

示例 2：

<div class="example-block">
输入：nums = [0,-1], queries = [[0,-5]]

输出：0

解释： 
执行第 1 个查询后，<code>nums = [-5,-1]</code>，不包含相邻元素的子序列的最大和为 0（选择空子序列）。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 104</code></li>
	<li><code>-105 &lt;= nums[i] &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 5 * 104</code></li>
	<li><code>queries[i] == [posi, xi]</code></li>
	<li><code>0 &lt;= posi &lt;= nums.length - 1</code></li>
	<li><code>-105 &lt;= xi &lt;= 105</code></li>
</ul>