Given an array of POSITIVE INTEGERS, find the greatest sum that can be generated without adding 2 numbers positioned next to each other.
arr = [7, 12, 4, 18, 2, 6]
36
The maximum sum that can be generated is 36, by adding 12, 18 and 6 which are not adjacent to each other.
arr = [7, 10, 12, 7, 9, 14]
33
The maximum sum that can be generated is 33, by adding 7, 12 and 14 which are not adjacent to each other.
1 <= arr[i] <= 100
1 <= arr.length <= 50
Click to reveal
Can you try using another array to store the results up until that index while traversing the array? Can you try using a Dynamic Programming approach?
Click to reveal
The formula that will help you is
max((i - 1)value, (i - 2)value + i value)