Maximum sum such that no two elements are adjacent


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 -

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

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

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