Maximum Sum with No Two Consecutive Elements

Given an array of positive numbers, find the maximum sum of a subsequence such that no two numbers in the subsequence are adjacent in the original array. This is also commonly known as the House Robber problem.

Examples

Example 1

• Input Array: [5, 5, 10, 100, 10, 5]
• Output: 110
• Explanation: Choose elements 5 (index 0), 100 (index 3), and 5 (index 5). Total sum = 5 + 100 + 5 = 110.

Example 2

• Input Array: [3, 2, 7, 10]
• Output: 13
• Explanation: Choose elements 3 (index 0) and 10 (index 3). Total sum = 3 + 10 = 13.

Example 3

• Input Array: [3, 2, 5, 10, 7]
• Output: 15
• Explanation: Choose elements 3 (index 0), 5 (index 2), and 7 (index 4). Total sum = 3 + 5 + 7 = 15.

Dynamic Programming Recurrence

Let dp[i] represent the maximum sum of a subsequence from the subarray arr[0..i] such that no two elements are adjacent.

For each element arr[i], we have two options:

1. Exclude arr[i]: The maximum sum remains the same as the maximum sum up to the previous index. value_exclude = dp[i-1]
2. Include arr[i]: The maximum sum becomes arr[i] plus the maximum sum up to index i-2 (since we cannot pick adjacent arr[i-1]). value_include = arr[i] + dp[i-2]

Therefore, the recurrence relation is: dp[i] = max(dp[i-1], arr[i] + dp[i-2])

Base Cases

• dp[0] = arr[0]
• dp[1] = max(arr[0], arr[1])

1. DP Tabulation Solution - O(N) Space

function maxSumNonAdjacentTabulation(arr) {
    const n = arr.length;
    if (n === 0) return 0;
    if (n === 1) return arr[0];
 
    const dp = new Array(n);
 
    // Initialize base cases
    dp[0] = arr[0];
    dp[1] = Math.max(arr[0], arr[1]);
 
    // Fill table bottom-up
    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]);
    }
 
    return dp[n - 1];
}

2. Space Optimized DP Solution - O(1) Space

Notice that to compute dp[i], we only need the values of dp[i-1] and dp[i-2]. Therefore, we can optimize space complexity by keeping track of only the previous two maximum sums using two variables.

function maxSumNonAdjacentSpaceOptimized(arr) {
    const n = arr.length;
    if (n === 0) return 0;
    if (n === 1) return arr[0];
 
    // Represents dp[i-2]
    let prev2 = arr[0];
    // Represents dp[i-1]
    let prev1 = Math.max(arr[0], arr[1]);
 
    for (let i = 2; i < n; i++) {
        // Current max is the max of including arr[i] or excluding arr[i]
        const curr = Math.max(prev1, arr[i] + prev2);
        prev2 = prev1;
        prev1 = curr;
    }
 
    return prev1;
}
 
// Driver code
const arr = [5, 5, 10, 100, 10, 5];
console.log("Maximum sum is:", maxSumNonAdjacentSpaceOptimized(arr));
// Output: Maximum sum is: 110

Complexity Analysis

• Time Complexity: O(N)
  • We traverse the array of length N exactly once.
• Space Complexity:
  • O(N) for the standard Tabulation approach.
  • O(1) for the Space-Optimized approach (uses only constant variables).