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

We are going to use dynamic programming to essentially
`remember`

the results of our previous iterations.

- Create an array called
`maxSubsetSum`

which will contain the Maximum Possible Sum with NO Adjacent elements UP UNTIL THAT INDEX. - The formula that we are going to use is

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

- The
`maxSubsetSum[0]`

will be equal to`arr[0]`

- This is because the first element will be the maximum till first index. - The
`maxSubsetSum[1]`

value will be the MAXIMUM of`arr[0]`

and`arr[1]`

. - Run a for / while loop over the given
`array`

and use the formula to calculate`maxSubsetSum[i]`

. - The
`maxSubarraySum[i-2] + 1`

ensures that we are ONLY taking NON-ADJACENT values in our selections.

`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.

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.

`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.

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