Maximum Sum of Subsequence With Non-adjacent Elements
You are given an array nums consisting of integers. You are also given a 2D array queries, where queries[i] = [posi, xi].
For query i, first set nums[posi] equal to xi, then calculate the answer to query i, which is the maximum sum of a subsequence of nums 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 10^9 + 7.
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.
Example 1
Input
nums = [3,5,9], queries = [[1,-2],[0,-3]]Output
21After the first query, the maximum non-adjacent subsequence sum is 12, and after the second query it is 9, so the total is 21.
Example 2
Input
nums = [0,-1], queries = [[0,-5]]Output
0After the first query, choosing an empty subsequence gives the maximum sum of 0.
Constraints
- 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
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.