Maximum sum such that no 2 elements are adjacent

Problem Statement

Given an array of positive integers, find the maximum sum of a subsequence such that no two elements are adjacent in the original array.

Constraints:

• All elements are positive integers
• Array has at least one element

Example:

• Input: arr = [5, 5, 10, 100, 10, 5]
• Output: 110
• Explanation: Pick 5 + 100 + 5 = 110 (indices 0, 3, 5)

Example 2:

• Input: arr = [1, 2, 3]
• Output: 4
• Explanation: Pick 1 + 3 = 4 (indices 0, 2)

Example 3:

• Input: arr = [1, 20, 3]
• Output: 20
• Explanation: Pick 20 alone

Approach 1: Brute Force (Recursion)

Intuition

For each element, we have two choices: include it or exclude it. If we include it, we skip the next element. Try all combinations and find the maximum.

Algorithm

1. At each index i, either:
   • Include arr[i] and recurse from i+2
   • Exclude arr[i] and recurse from i+1
2. Return the maximum of both choices
3. Base case: if index >= n, return 0

public class Solution {
    public int maxSumRecursive(int[] arr, int i) {
        // Base case
        if (i >= arr.length) {
            return 0;
        }
        
        // Include current element
        int include = arr[i] + maxSumRecursive(arr, i + 2);
        
        // Exclude current element
        int exclude = maxSumRecursive(arr, i + 1);
        
        return Math.max(include, exclude);
    }
    
    public int findMaxSum(int[] arr) {
        return maxSumRecursive(arr, 0);
    }
}

Complexity Analysis

• Time Complexity: O(2ⁿ) - Each element has two choices
• Space Complexity: O(n) - Recursion stack

Approach 2: Memoization (Top-Down DP)

Intuition

The recursive solution has overlapping subproblems. Use memoization to store results.

public class Solution {
    private int[] memo;
    
    public int maxSumMemo(int[] arr, int i) {
        if (i >= arr.length) {
            return 0;
        }
        
        if (memo[i] != -1) {
            return memo[i];
        }
        
        int include = arr[i] + maxSumMemo(arr, i + 2);
        int exclude = maxSumMemo(arr, i + 1);
        
        memo[i] = Math.max(include, exclude);
        return memo[i];
    }
    
    public int findMaxSum(int[] arr) {
        memo = new int[arr.length];
        Arrays.fill(memo, -1);
        return maxSumMemo(arr, 0);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each subproblem solved once
• Space Complexity: O(n) - Memoization array + recursion stack

Approach 3: Tabulation (Bottom-Up DP)

Intuition

Build the solution iteratively from the end. dp[i] represents the maximum sum starting from index i.

public class Solution {
    public int findMaxSum(int[] arr) {
        int n = arr.length;
        
        if (n == 0) return 0;
        if (n == 1) return arr[0];
        if (n == 2) return Math.max(arr[0], arr[1]);
        
        int[] dp = new int[n];
        
        dp[n - 1] = arr[n - 1];
        dp[n - 2] = Math.max(arr[n - 2], arr[n - 1]);
        
        for (int i = n - 3; i >= 0; i--) {
            dp[i] = Math.max(arr[i] + dp[i + 2], dp[i + 1]);
        }
        
        return dp[0];
    }
}

Alternative: Forward DP

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(n) - DP array

Approach 4: Space Optimized DP (Optimal)

Intuition

We only need the last two values to compute the current value.

Algorithm

1. Maintain two variables: prev1 (i-1) and prev2 (i-2)
2. For each element, compute max(arr[i] + prev2, prev1)
3. Update prev2 = prev1, prev1 = current

public class Solution {
    public int findMaxSum(int[] arr) {
        int n = arr.length;
        
        if (n == 0) return 0;
        if (n == 1) return arr[0];
        
        int prev2 = 0;          // Max sum not including previous element
        int prev1 = arr[0];     // Max sum including up to previous element
        
        for (int i = 1; i < n; i++) {
            int current = Math.max(arr[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Only two variables

Variation: Circular Array (House Robber II)

If the array is circular (first and last elements are adjacent):

Key Takeaways

1. Classic DP Problem: This is the famous "House Robber" problem
2. Recurrence Relation: dp[i] = max(arr[i] + dp[i-2], dp[i-1])
3. Space Optimization: Only need last two values, reducing O(n) to O(1) space
4. Greedy Doesn't Work: Can't just pick alternate elements or largest elements
5. Circular Variation: Split into two linear subproblems
6. Applications: Resource allocation, scheduling, stock picking