Maximum sum such that no two elements are adjacent

general
1

Hi,

I was trying out an alternate approach for solving the subject problem - I would have 1 indexed input array (with the 0th element of the input array = 0). I will have a 1 index dp array with dp[0] = 0 and dp[1] = input_array[1]. I would then use this :

i = 2 to n
dp[i] = max( dp[i-2] + input_array[i], dp[i-1] )

I’ve been trying this here : bqVDKj - Online C++0x Compiler & Debugging Tool - Ideone.com

Can you please let me know why is this wrong ?
P.S. - I’m sure this is wrong while testing on this : SFRV Problem - CodeChef

2

Your code for “Maximum_sum_…adj” using dp should work. It seems to be to logically correct and also worked on multiple test cases that i tried.
For SFRV, refer
https://www.codechef.com/viewsolution/30599540

this solution uses dp approach. where array f is your dp array.