My approach:

Link to my code is:

https://www.codechef.com/viewsolution/24118775

In the code dp[i] represents the maximum sum you can form without selecting adjacent elements when you have only first(i+1) ie,“0,1,2,…i” elements, so basically dp[i] is the answer when there are “i+1” elements.

My approach:

To calculate dp[i], there can be 2 cases:

- When the answer to dp[i] does not contain A[i] element, then dp[i]=dp[i-1]
- When the answer to dp[i] contains A[i] element, then

dp[i]=max(A[i],A[i]+dp[i-2])

Ans the final answer to dp[i]=max(ans of case 1, ans of case 2).

I have thought a few times but can’t figure out what is wrong with this approach. Any help would be appreciated.