Tap here to switch tabs
Problem
Submissions

Problem: Maximum Sum of Subsequence With Non-adjacent Elements

Try to solve the Maximum Sum of Subsequence With Non-adjacent Elements problem.

Statement

You are given an integer array nums and a 2D2 {D} integer array queries, where each queries[i] = [pos_i, x_i].

For each query, perform the following operations:

  1. Update nums[pos_i] to x_i.

  2. Compute the maximum sum of a subsequence of nums such that no two selected elements are adjacent.

Return the sum of the answers to all queries. Since the answer may be very large, return it modulo 109+710^9 + 7.

Note: An empty subsequence is considered valid and has a sum of 00.

Constraints:

  • 1≤1 \leq nums.length ≤5×104\leq 5 \times 10^4

  • −105≤-10^5 \leq nums[i] ≤105\leq 10^5

  • 1≤1 \leq queries.length ≤5×104\leq 5 \times 10^4

  • queries[i] == [pos_i, x_i]

  • 0≤0 \leq pos_i ≤\leq nums.length −1- 1

  • −105≤-10^5 \leq x_i ≤105\leq 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Sum of Subsequence With Non-adjacent Elements

Try to solve the Maximum Sum of Subsequence With Non-adjacent Elements problem.

Statement

You are given an integer array nums and a 2D2 {D} integer array queries, where each queries[i] = [pos_i, x_i].

For each query, perform the following operations:

  1. Update nums[pos_i] to x_i.

  2. Compute the maximum sum of a subsequence of nums such that no two selected elements are adjacent.

Return the sum of the answers to all queries. Since the answer may be very large, return it modulo 109+710^9 + 7.

Note: An empty subsequence is considered valid and has a sum of 00.

Constraints:

  • 1≤1 \leq nums.length ≤5×104\leq 5 \times 10^4

  • −105≤-10^5 \leq nums[i] ≤105\leq 10^5

  • 1≤1 \leq queries.length ≤5×104\leq 5 \times 10^4

  • queries[i] == [pos_i, x_i]

  • 0≤0 \leq pos_i ≤\leq nums.length −1- 1

  • −105≤-10^5 \leq x_i ≤105\leq 10^5