3165. Maximum Sum of Subsequence With Non-adjacent Elements Hard

1/**
2 * [3165] Maximum Sum of Subsequence With Non-adjacent Elements
3 *
4 * You are given an array nums consisting of integers. You are also given a 2D array queries, where queries[i] = [posi, xi].
5 * For query i, we first set nums[posi] equal to xi, then we calculate the answer to query i which is the maximum sum of a <span data-keyword="subsequence-array">subsequence</span> of nums where no two adjacent elements are selected.
6 * Return the sum of the answers to all queries.
7 * Since the final answer may be very large, return it modulo 10^9 + 7.
8 * 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.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">nums = [3,5,9], queries = [[1,-2],[0,-3]]</span>
13 * Output: <span class="example-io">21</span>
14 * Explanation:<br />
15 * After the 1^st query, nums = [3,-2,9] and the maximum sum of a subsequence with non-adjacent elements is 3 + 9 = 12.<br />
16 * After the 2^nd query, nums = [-3,-2,9] and the maximum sum of a subsequence with non-adjacent elements is 9.
17 * </div>
18 * <strong class="example">Example 2:
19 * <div class="example-block">
20 * Input: <span class="example-io">nums = [0,-1], queries = [[0,-5]]</span>
21 * Output: <span class="example-io">0</span>
22 * Explanation:<br />
23 * After the 1^st query, nums = [-5,-1] and the maximum sum of a subsequence with non-adjacent elements is 0 (choosing an empty subsequence).
24 * </div>
25 *  
26 * Constraints:
27 * 
28 * 	1 <= nums.length <= 5 * 10^4
29 * 	-10^5 <= nums[i] <= 10^5
30 * 	1 <= queries.length <= 5 * 10^4
31 * 	queries[i] == [posi, xi]
32 * 	0 <= posi <= nums.length - 1
33 * 	-10^5 <= xi <= 10^5
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/
39// discuss: https://leetcode.com/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn maximum_sum_subsequence(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_3165() {
57    }
58}
59