Maximum Sum of Subsequence With Non-adjacent Elements - Video Solutions

Problem Overview: Given an integer array, select a subsequence of elements such that no two chosen elements are adjacent and the total sum is maximized. Some variants also include update queries where array values change and the maximum non‑adjacent subsequence sum must be recomputed efficiently.

Approach 1: Recursive with Memoization (Top‑Down DP) (Time: O(n), Space: O(n))

This approach models the problem as a decision at each index: either take the current element and skip the next one, or skip the current element entirely. A recursive function explores both choices. Memoization stores results for each index so the same subproblem is not recomputed. The recurrence is dp[i] = max(nums[i] + dp[i+2], dp[i+1]). This method is useful for understanding the structure of the problem and how overlapping subproblems arise in dynamic programming.

Approach 2: Iterative Dynamic Programming (Bottom‑Up) (Time: O(n), Space: O(n))

The recursive recurrence can be converted into a bottom‑up DP table. Iterate through the array while maintaining the best sum achievable up to each index. For each position i, compute dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The value dp[i-1] represents skipping the element, while dp[i-2] + nums[i] represents taking it. This version avoids recursion overhead and is commonly used in interview settings because it clearly shows the transition logic.

Approach 3: Optimized Dynamic Programming with Prefix State (Time: O(n), Space: O(1))

The DP table only depends on the previous two states, so storing the entire array is unnecessary. Maintain two variables: prev1 (best sum up to previous index) and prev2 (best sum up to index‑2). For each element, compute current = max(prev1, prev2 + nums[i]). Then shift the variables forward. This reduces memory to constant space while keeping the same O(n) time complexity. It is the most practical implementation for the classic non‑adjacent subsequence problem.

Approach 4: Segment Tree for Dynamic Updates (Time: O((n + q) log n), Space: O(n))

When the array receives updates and the maximum non‑adjacent subsequence sum must be recomputed after each change, a segment tree becomes effective. Each node stores multiple states representing whether the segment starts or ends with a chosen element. During merges, these states combine while respecting the non‑adjacent constraint. Updates modify a single index and propagate upward in O(log n). This technique handles large numbers of queries efficiently while maintaining correct subsequence constraints.

Recommended for interviews: Start with the recursive recurrence to demonstrate understanding of the decision process. Interviewers usually expect the iterative dynamic programming solution with O(n) time and O(1) space. If the problem includes update queries, recognizing that a segment tree with state merging is required demonstrates stronger algorithmic design skills.