Hard

Maximum Sum of Subsequence With Non-adjacent Elements

LAB

Given an integer array nums and a list of queries, apply every query [index, value] in order by permanently setting nums[index] to value. After each update, find the maximum sum of a subsequence whose selected indices are never adjacent. The empty subsequence is allowed, so the maximum is never negative. Add the maximum after every query and return the total modulo 1,000,000,007.

EXAMPLES

Example 1

Input
{
  "nums": [
    3,
    5,
    9
  ],
  "queries": [
    [
      1,
      -2
    ],
    [
      0,
      -3
    ]
  ]
}

Output
21

FUNCTION SHAPE

nums: intArrayqueries: intMatrix→int

SOLUTION NOTE

The state stores a boundary contract, not four unrelated answers. Do not take modulo inside the DP: comparisons require the true sums. Apply modulo only while accumulating the answers across queries.

Reveal reference solution +

pythonREFERENCE

from typing import List

NEG = -(10**30)
MOD = 1_000_000_007

def leaf(x: int):
    return [[0, NEG], [NEG, x]]

def merge(left, right):
    return [[
        max(
            left[a][0] + right[0][b],
            left[a][1] + right[0][b],
            left[a][0] + right[1][b],
        )
        for b in range(2)
    ] for a in range(2)]

class Solution:
    def maximumSumSubsequence(
        self, nums: List[int], queries: List[List[int]]
    ) -> int:
        n = len(nums)
        tree = [None] * (4 * n)

        def build(node: int, lo: int, hi: int) -> None:
            if lo == hi:
                tree[node] = leaf(nums[lo])
                return
            mid = (lo + hi) // 2
            build(node * 2, lo, mid)
            build(node * 2 + 1, mid + 1, hi)
            tree[node] = merge(tree[node * 2], tree[node * 2 + 1])

        def update(node: int, lo: int, hi: int, index: int, value: int) -> None:
            if lo == hi:
                tree[node] = leaf(value)
                return
            mid = (lo + hi) // 2
            if index <= mid:
                update(node * 2, lo, mid, index, value)
            else:
                update(node * 2 + 1, mid + 1, hi, index, value)
            tree[node] = merge(tree[node * 2], tree[node * 2 + 1])

        build(1, 0, n - 1)
        answer = 0
        for index, value in queries:
            update(1, 0, n - 1, index, value)
            answer = (answer + max(map(max, tree[1]))) % MOD
        return answer

def solve(nums, queries):
    return Solution().maximumSumSubsequence(nums, queries)

TimeO(n + q log n)

SpaceO(n)

Open on LeetCode ↗