# Maximum Subset Sum With No Adjacent

Given an array of POSITIVE INTEGERS, find the greatest sum that can be generated without adding 2 numbers positioned next to each other.

## 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])
``````
1. The `maxSubsetSum[0]` will be equal to `arr[0]` - This is because the first element will be the maximum till first index.
2. The `maxSubsetSum[1]` value will be the MAXIMUM of `arr[0]` and `arr[1]`.
3. Run a for / while loop over the given `array` and use the formula to calculate `maxSubsetSum[i]`.
4. 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.
Solve Maximum Subset Sum With No Adjacent on Algochurn

## Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn