Maximum Subset Sum With No Adjacent

Dynamic Programming

We are going to use dynamic programming to essentially remember the results of our previous iterations.

1. Create an array called maxSubsetSum which will contain the Maximum Possible Sum with NO Adjacent elements UP UNTIL THAT INDEX.
2. The formula that we are going to use is

MAX(maxSubsetSum[i-1], maxSubsetSum[i-2] + arr[i])

3. The maxSubsetSum[0] will be equal to arr[0] - This is because the first element will be the maximum till first index.
4. The maxSubsetSum[1] value will be the MAXIMUM of arr[0] and arr[1].
5. Run a for / while loop over the given array and use the formula to calculate maxSubsetSum[i].
6. The maxSubarraySum[i-2] + 1 ensures that we are ONLY taking NON-ADJACENT values in our selections.

Time and Space Complexities

• O(n) - Time because we have to iterate over all the elements atleast once
• O(n) - Space because we are storing the results in the maxSubsetSum array.

Dynamic Programming - Better space complexity

Everything is same as seen in the second solution, except for the array that we used in the previous solution.

If you closely observe, we are only going to use ATMOST 2 values from the maxSubarraySum array, those are maxSubarraySum[i-1] and maxSubarraySum[i-2].

Hence, this solution removes the need of the extra maxSubarraySum and introduces first and second variables to keep track of i and i-1 values.

Time and Space Complexities

• O(n) - Time because we have to iterate over all the elements atleast once
• O(1) - Space we are only using first and second variables.