We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum of Subsequence With Non-adjacent Elements

Number: 3423

Difficulty: Hard

Paid? No

Companies: Google, Infosys

Problem Description

Given an integer array nums and a list of queries where each query updates an element in nums, after each update you must compute the maximum sum that can be obtained by selecting a subsequence such that no two chosen elements are adjacent. (An empty subsequence is allowed, which gives a sum of 0.) Return the sum of the answers for all queries modulo 10^9+7.

Key Insights

  • This is the “House Robber” style problem but with dynamic updates.
  • A naïve re‐computation via dynamic programming for each query would be O(n) per query, which is too slow.
  • We can design a segment tree where each node stores enough DP information so that segments can be merged quickly.
  • By formulating each index as a “segment” that gives two outcomes depending on whether you are allowed to choose that element (if the previous element was not chosen) or forced to skip it (if the previous element was chosen), we can merge segments via a “DP transition.”
  • Merging two segments is analogous to “matrix multiplication” – for a given starting state (allowed vs. not allowed) we try both possibilities for the ending state of the left segment and use that as input for the right segment.

Space and Time Complexity

Time Complexity: O((n + q) * log n), where n is the size of nums and q is the number of queries (each update takes O(log n)). Space Complexity: O(n) for the segment tree.

Solution

We solve the problem by modeling the non-adjacent subsequence selection as a DP that works on intervals. For each index i we consider two states:

  1. State 0 (free): the previous element was not selected so we can decide to pick nums[i] (if it is beneficial) or skip it.
  2. State 1 (forced skip): the previous element was selected, so we must skip the current element.

For each element, we build a 2×2 DP “transition matrix” T such that: • T[0][0] = 0 means that if we are allowed to pick and we skip the element, we add 0. • T[0][1] = nums[i] if nums[i] > 0 (or –∞ if nums[i] is negative) which represents picking the element. • T[1][0] = 0 because when forced to skip, the only option is to skip. • T[1][1] = –∞ since you cannot pick when forced.

We denote –∞ as a very small number (e.g. MIN = -10^18) to ensure we never choose invalid transitions.

To merge two segments (with matrices A and B), the new transition matrix V is computed as:   V[s][t] = max( A[s][r] + B[r][t] ) for r in {0, 1}, and for every starting state s and ending state t. The overall answer for the current nums array after a query is then:   max( TreeRoot[0][0], TreeRoot[0][1] ) (using 0 as the initial “free” state because no element precedes index 0).

A segment tree is built with these matrices at its leaves and uses our merge function at internal nodes. On each query, we update one leaf in O(log n) time and then read the result at the tree’s root.

Code Solutions

# Define a very small number to represent negative infinity.
MIN = -10**18  
MOD = 10**9 + 7

# Segment tree node stores a 2x2 matrix dp where:
# dp[s][t] = maximum sum for the segment if starting with state "s" (0=free, 1=forced skip)
# and ending with state "t" (0=last element not selected, 1=last element selected)

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        # Initialize tree with 2x2 matrices for each node
        self.tree = [ [[0, MIN], [0, MIN]] for _ in range(2*self.size) ]
        # Build leaves
        for i in range(self.n):
            self.tree[self.size + i] = self.make_leaf(nums[i])
        # Build internal nodes by merging children
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[2*i], self.tree[2*i+1])
            
    def make_leaf(self, value):
        # For a leaf node at index i based on value
        # If previous element is free (state 0) then:
        #   if we skip: state becomes 0 and contribution is 0.
        #   if we take: state becomes 1 and contribution is value if value > 0 else -infinity.
        # If previous element is forced (state 1), we can only skip.
        return [
            [0, value if value > 0 else MIN],
            [0, MIN]
        ]
        
    def merge(self, left, right):
        # Merging two segments by a DP transition (like matrix multiplication)
        # For each starting state s in left and ending state t in right,
        # we try both possibilities for the junction state r.
        res = [[MIN, MIN], [MIN, MIN]]
        for s in range(2):
            for t in range(2):
                for r in range(2):
                    res[s][t] = max(res[s][t], left[s][r] + right[r][t])
        return res
        
    def update(self, idx, value):
        # Update a leaf at index idx with new value and rebuild segment tree upwards.
        pos = idx + self.size
        self.tree[pos] = self.make_leaf(value)
        pos //= 2
        while pos:
            self.tree[pos] = self.merge(self.tree[2*pos], self.tree[2*pos+1])
            pos //= 2
            
    def query(self):
        # The answer is computed starting with state 0.
        res = self.tree[1]
        return max(res[0][0], res[0][1])
        
def maximumSumQueries(nums, queries):
    segTree = SegmentTree(nums)
    total = 0
    for pos, new_val in queries:
        # Update the value at index pos.
        segTree.update(pos, new_val)
        # Query the segment tree: answer is max sum given state 0.
        total = (total + segTree.query()) % MOD
    return total

# Example usage:
if __name__ == '__main__':
    nums1 = [3,5,9]
    queries1 = [[1,-2],[0,-3]]
    print(maximumSumQueries(nums1, queries1))  # Expected output: 21

    nums2 = [0,-1]
    queries2 = [[0,-5]]
    print(maximumSumQueries(nums2, queries2))  # Expected output: 0
← Back to All Questions