Encoding April 2019, Need help in AVN007

help
1

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:

  1. When the answer to dp[i] does not contain A[i] element, then dp[i]=dp[i-1]
  2. 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.

2

There is a strange case, when n = 1 do not print anything, it is not your fault :slight_smile:

1 Like
3

That’s bizarre, is there any logic/reason behind it? If not, how come those who have solved it during the contest figured it out?