Maximum sum of non adjacent elements

Return nonadjacent subsequence of array with maximum sum

Maximum Sum of Non-Adjacent Elements

Problem Statement

Given an integer array, nums, of size n, return the maximum possible sum using elements of nums, such that no two chosen elements are adjacent to each other in the array.

Examples

Example 1

Input: nums = [1, 2, 4]

Output: 5

Explanation: From [1, 2, 4], picking 1 and 4 (which are not adjacent) gives the maximum sum of 5.

Example 2

Input: nums = [2, 1, 4, 9]

Output: 11

Explanation: From [2, 1, 4, 9], picking 2 and 9 (which are not adjacent) gives the maximum sum of 11.

Solution

Since we need to consider every possible combination of non-adjacent elements, this calls for recursion. At each index, we have two choices: pick the current element, or don't pick it. We take whichever choice leads to the larger sum.

This is solved using four progressive approaches: plain recursion, memoization, tabulation, and space optimization.

1. Brute Force (Plain Recursion)

• At each index, we calculate two options:
  • Pick the current element: add its value to the best result from two indices back (since we can't pick its immediate neighbor).
  • Don't pick it: just take the best result from one index back.
• We return whichever of these two options is larger.
• The base cases are: at index 0, the answer is simply nums[0]. For any index less than 0, there's nothing to pick, so the answer is 0.

nonAdjacent(nums) {
    let mini = -Infinity;

    function recurr(index) {
      if (index === 0) {
        return nums[0];
      }

      if (index < 0) {
        return 0;
      }

      let pick = nums[index] + recurr(index - 2);
      let notPick = recurr(index - 1);
      return (mini = Math.max(pick, notPick));
    }

    recurr(nums.length - 1);
    return mini;
}

This works, but it recalculates the same subproblems many times, making it slow for larger arrays.

2. Memoization (Top-Down)

We use the same recursive logic, but store each index's result in a memo array the first time we calculate it, so we never solve the same subproblem twice.

nonAdjacent(nums) {
    if (nums.length === 0) return 0;
    let memo = Array(nums.length).fill(-1);
    memo[0] = nums[0];

    function recurr(index, memo) {
      if (index === 0) {
        return memo[0];
      }

      if (index < 0) {
        return 0;
      }

      if (memo[index] !== -1) {
        return memo[index];
      }

      let pick = nums[index] + recurr(index - 2, memo);
      let notPick = recurr(index - 1, memo);

      memo[index] = Math.max(pick, notPick);
      return memo[index];
    }

    recurr(nums.length - 1, memo);
    return memo[nums.length - 1];
}

3. Tabulation (Bottom-Up)

Instead of starting from the last index and recursing backward, we start from the beginning of the array and build our way forward, filling in the dp array as we go.

nonAdjacent(nums) {
    if (nums.length === 0) return 0;
    let dp = Array(nums.length).fill(-1);

    dp[0] = nums[0];

    for (let i = 1; i < nums.length; i++) {
      let pick = nums[i];

      if (i > 1) {
        pick += dp[i - 2];
      }

      let notPick = dp[i - 1];

      dp[i] = Math.max(pick, notPick);
    }

    return dp[nums.length - 1];
}

4. Space Optimization

Since calculating dp[i] only ever needs the results from the previous two indices, we don't need to keep the whole dp array around. We can just track those two values using two variables.

nonAdjacent(nums) {
    if (nums.length === 0) return 0;

    let prev1 = nums[0];
    let prev2 = 0;

    for (let i = 1; i < nums.length; i++) {
      let pick = nums[i];

      if (i > 1) {
        pick += prev2;
      }

      let notPick = prev1;

      let curr = Math.max(pick, notPick);

      prev2 = prev1;
      prev1 = curr;
    }

    return prev1;
}

This final version runs in O(n) time, using only O(1) extra space.