mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
46 lines
2.4 KiB
HTML
46 lines
2.4 KiB
HTML
<p>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] = [pos<sub>i</sub>, x<sub>i</sub>]</code>.</p>
|
|
|
|
<p>For query <code>i</code>, we first set <code>nums[pos<sub>i</sub>]</code> equal to <code>x<sub>i</sub></code>, then we calculate the answer to query <code>i</code> which is the <strong>maximum</strong> sum of a <span data-keyword="subsequence-array">subsequence</span> of <code>nums</code> where <strong>no two adjacent elements are selected</strong>.</p>
|
|
|
|
<p>Return the <em>sum</em> of the answers to all queries.</p>
|
|
|
|
<p>Since the final answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>
|
|
|
|
<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [3,5,9], queries = [[1,-2],[0,-3]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">21</span></p>
|
|
|
|
<p><strong>Explanation:</strong><br />
|
|
After the 1<sup>st</sup> query, <code>nums = [3,-2,9]</code> and the maximum sum of a subsequence with non-adjacent elements is <code>3 + 9 = 12</code>.<br />
|
|
After the 2<sup>nd</sup> query, <code>nums = [-3,-2,9]</code> and the maximum sum of a subsequence with non-adjacent elements is 9.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [0,-1], queries = [[0,-5]]</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">0</span></p>
|
|
|
|
<p><strong>Explanation:</strong><br />
|
|
After the 1<sup>st</sup> query, <code>nums = [-5,-1]</code> and the maximum sum of a subsequence with non-adjacent elements is 0 (choosing an empty subsequence).</p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= nums.length <= 5 * 10<sup>4</sup></code></li>
|
|
<li><code>-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= queries.length <= 5 * 10<sup>4</sup></code></li>
|
|
<li><code>queries[i] == [pos<sub>i</sub>, x<sub>i</sub>]</code></li>
|
|
<li><code>0 <= pos<sub>i</sub> <= nums.length - 1</code></li>
|
|
<li><code>-10<sup>5</sup> <= x<sub>i</sub> <= 10<sup>5</sup></code></li>
|
|
</ul>
|