DP - 23: Find maximum sum of array elements if consecutive elements are not allowed

Solution:
- We solve it using DP Bottom up solution
- For every value, either we include this or we exclude this
- To find maximum Sum received, we get the maximum of both solution (including, excluding)
- We take array to storage values & once we're done, we return the last value as answer

Time Complexity: O(n)
Space Complexity: O(n)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[badarikrishna]

Hi, just want to tell you even though you have less views this is the best explanation I found. Keep doing your work..!! 🙌🙌

[abhimalyachowdhury]

Cannot believe such an elegant solution existed for this problem...previously tried with recursion...But this one is just awesome!!

[abyxatjov]

Nice solution. Here's my python code time - O(n), space - O(1) - this improvement to your solution is quite easy - you only use the last 2 values so you can just store them in 2 variables, with most languages additionally requiring temp variable to swap them.
def max_sum_neighborless(lst):
if not lst:
return 0
fst = max(lst[0], 0)
if len(lst) == 1:
return fst
snd = max(lst[1], fst)
for i in range(2, len(lst)):
fst, snd = snd, max(snd, fst + lst[i])
return snd

[pooranik]

Thank you so much.i could easily understand with the help of ur teaching skill.
You are really awesome.Keep up the good work.

[davindjayadi]

Well explained 👏👏👏 keep up the good works 🔥🔥🔥

[selvalooks]

clear solution !!! simple and effective !!!

[abhishekjaiswal]

great explanation bhaiya, appreciable

[abhinaygupta]

i think this won't work if array has negative elements. the include condition can be changed to dp[i]= max(arr[i], dp[i-1], arr[i]+dp[i-2])

[siddhantbhatia]

bhai agar array me negative numbers hue toh maximum of dp[i-1], a[i]+dp[i-2] aur a[i] bhi lena padhega. ye aapka code is correct for positive numbers but negative numbers me thoda sa mistake hojayega jaise agar array hua {-1, -1, -2, 10}

[omarbousbia]

Great video. But does anyone know leetcode link for this problem?

[raviteja-csdr]

the code will fail for
3
-100 -99 2
answer should be 2
but above solution gives -99

[engyassem]

how can i get the indices of the elements that were summed

[TheCalabir]

Thanks for the explanation, I finally understood how the logic can be abstracted from this problem, let me paste the implementation in Scala using tail recursion: