[Algorithm] DP - 03. Max Subset Sum No Adjacent

Write a function that takes in an array of positive integers and returns the maximum sum of non-adjacent elements in the array.

If the input array is empty, the function should return 0.

Sample Input

array = [75, 105, 120, 75, 90, 135]

Sample Output

330 // 75 + 120 + 135

Normal approach:

// Time: O(N)
// Space: O(N)
function maxSubsetSumNoAdjacent(array) {
  if (array.length === 0) {
    return 0
  }

  const dp = Array.from(array, (val, i) => {
    if (i === 0) {
      return val
    } else if (i === 1) {
      return Math.max(array[0], array[1])
    } else {
      return 0
    }
  })

  for (let i = 2; i < array.length; i++) {
    if (dp[i-2] + array[i] > dp[i-1]) {
      dp[i] = dp[i-2] + array[i] 
    } else {
      dp[i] = dp[i-1]
    }
  }

  return dp[dp.length - 1]
}

// Do not edit the line below.
exports.maxSubsetSumNoAdjacent = maxSubsetSumNoAdjacent;

It can be improved to:

// Time: O(N)
// Space: O(1)

We don't need to track the whole dp array, and loop from beginning to current i position to get max sum.

What we can do for this task is that we only need to keep tracking two values, a samll slice window.

if ary[i] + dp[0] > dp[1]
  dp[0] = dp[1]
  dp[1] = ary[i] + dp[0]
else
  dp[0] = dp[1]

function maxSubsetSumNoAdjacent(array) {
  if (array.length === 0) {
    return 0
  }

  const dp = [0, 0]
  
  for (let i = 0; i < array.length; i++) {
    if (dp[0] + array[i] > dp[1]) {
      const val = dp[0] + array[i]
      dp[0] = dp[1]
      dp[1] = val
    } else {
      dp[0] = dp[1]
    }
  }

  return dp[1]
}

// Do not edit the line below.
exports.maxSubsetSumNoAdjacent = maxSubsetSumNoAdjacent;