3165. Maximum Sum of Subsequence With Non-adjacent Elements

Problem Link

Description

---

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, we first set nums[posi] equal to xi, then we 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 109 + 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: 21

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

Example 2:

Input: nums = [0,-1], queries = [[0,-5]]

Output: 0

Explanation:
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).

 

Constraints:

• 1 <= nums.length <= 5 * 104
• -105 <= nums[i] <= 105
• 1 <= queries.length <= 5 * 104
• queries[i] == [posi, xi]
• 0 <= posi <= nums.length - 1
• -105 <= xi <= 105

Solution

---

Python3

class Node:
    def __init__(self, val=0, a=0, b=0, c=0):
        self.max_sum = max(0, val)
        self.exclude_first = a
        self.exclude_last = b
        self.exclude_first_last = c
 
class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [None] * (4 * self.n)        
        self.build(1, 0, self.n - 1, arr)
 
    def build(self, v, tl, tr, arr):
        if tl == tr:
            self.tree[v] = Node(arr[tl])
        else:
            tm = tl + (tr - tl) // 2
            self.build(v * 2, tl, tm, arr)
            self.build(v * 2 + 1, tm + 1, tr, arr)
            
            if tr - tl == 1:
                self.tree[v] = self.merge2(self.tree[v * 2], self.tree[v * 2 + 1])
            else:
                self.tree[v] = self.merge(self.tree[v * 2], self.tree[v * 2 + 1])
 
    def merge(self, left, right):
        node = Node()
 
        node.exclude_first = max(
            0,
            right.max_sum,
            left.exclude_first,
            right.exclude_first,
            right.exclude_last,
            left.exclude_first + right.exclude_first,
            right.max_sum + left.exclude_first_last
        )
 
        node.exclude_last = max(
            0,
            left.max_sum,
            left.exclude_first,
            left.exclude_last,
            left.max_sum + right.exclude_first_last,
            right.exclude_last + left.exclude_last
        )
 
        node.max_sum = max(
            0,
            node.exclude_first,
            node.exclude_last,
            left.max_sum + right.exclude_first,
            left.exclude_last + right.max_sum,
            left.max_sum,
            right.max_sum,
            left.exclude_last + right.exclude_last,
            left.exclude_first + right.exclude_first,
            left.exclude_last + right.exclude_first
        )
 
        node.exclude_first_last = max(
            0,
            left.exclude_first + right.exclude_first_last,
            right.exclude_last + left.exclude_first_last
        )
 
        return node
 
    def merge2(self, left, right):
        node = Node()
 
        node.exclude_first = max(0, right.max_sum)
        node.exclude_last = max(0, left.max_sum)
        node.max_sum = max(left.max_sum, right.max_sum)
        node.exclude_first_last = 0
 
        return node
 
    def query(self):
        return self.tree[1].max_sum
 
    def update(self, v, tl, tr, pos, value):
        if tl == tr:
            self.tree[v] = Node(value)
        else:
            tm = tl + (tr - tl) // 2
 
            if pos <= tm:
                self.update(v * 2, tl, tm, pos, value)
            else:
                self.update(v * 2 + 1, tm + 1, tr, pos, value)
 
            if tr - tl == 1:
                self.tree[v] = self.merge2(self.tree[v * 2], self.tree[v * 2 + 1])
            else:
                self.tree[v] = self.merge(self.tree[v * 2], self.tree[v * 2 + 1])
 
class Solution:
    def maximumSumSubsequence(self, nums, queries):
        N = len(nums)
        st = SegmentTree(nums)
        M = 10 ** 9 + 7
        res = 0
 
        for pos, value in queries:
            st.update(1, 0, N - 1, pos, value)
            res += st.query()
            if res >= M:
                res %= M
        
        return res