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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Sum of Subsequence With Non-adjacent Elements

Difficulty: Hard

Problem Description

You are given an array nums consisting of integers. You are also given a 2D array queries, where queries[i] = [pos_i, x_i]. For query i, we first set nums[pos_i] equal to x_i, 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 10^9 + 7.

Key Insights

  • The problem requires finding the maximum sum of a subsequence with non-adjacent elements after each query modification.
  • Adjustments to the array nums must be handled efficiently to avoid recalculating from scratch for each query.
  • Dynamic programming can be used to calculate the maximum sum of non-adjacent elements.
  • A Segment Tree can efficiently update and query ranges, which helps in adjusting and finding sums after each modification.

Space and Time Complexity

Time Complexity: O(n + q * log n)
Space Complexity: O(n)

Solution

The approach involves using dynamic programming alongside a Segment Tree. The idea is to maintain a DP array that calculates the maximum sum of non-adjacent elements. Upon receiving a query, the specified position in nums is updated, and the maximum sum is recalculated using the Segment Tree. This ensures that updates and queries are efficient, allowing the solution to handle the upper limits of constraints comfortably.

Code Solutions

def max_sum_subsequence(nums, queries):
    MOD = 10**9 + 7
    
    def calculate_max_sum():
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return max(0, nums[0])
        
        dp = [0] * n
        dp[0] = max(0, nums[0])
        dp[1] = max(dp[0], nums[1])
        
        for i in range(2, n):
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
        
        return dp[-1]
    
    total_sum = 0
    for pos, x in queries:
        nums[pos] = x
        total_sum = (total_sum + calculate_max_sum()) % MOD
    
    return total_sum
← Back to All Questions