Can you please share your code?
Your code is giving wrong output for the following test case:
1
5
5 3 2 4 1
ans must be 43, yours is giving 45ā¦
I think the reason behind the wrong solution is that you are hard selecting every alternative number which is positive ā¦ and this method has a fault. suppose you have the diff array as 4 5 -1 5 6 so there are various possibilities to choose numbers such as : 4 (INDEX 0) and then 5(index 3) which are non alternating as well but there are other possibilities as well like, choose 5(index 1) and 5(index 3) or choose 5(index 1) and 6(index 4) ā¦ In this case youāll choose 5 and 6 because there sum is 11(maximum) and they are non-alternating as wellā¦
If you look closely you will have two options each time, either to choose the elements or not chooseā¦ If chosen mark the element and make sure next element is not alternate to this oneā¦ This is a conventional DP bottom up method , slight modification to the 0/1 knapsackā¦
Pardon me if this is a very long answer, posting here for first time but I have explained the logic as best as I could. Please give it a read.
I used a different approach:
First calculate the base answer from the array with zero operations.
Now you can observe that if you have to swap two numbers a1 and a2 then net change in the base answer will be a1-a2. For example base answer for 7 6 3 2 is (7+12+9+8) i.e. 36.
Now if you swap 7 and 6 base answer will change by 1 (7-6), you can easily comprehend why is it so.
So, it all boils down to create a difference array of size n-1 and storing diff[i]=ar[i]-ar[i+1].
Then you have to find the maximum sum possible in array without using adjacent terms, as using adjacent terms of difference array will mean using the same number twice, which is not allowed.
Thus, you can find that sum easily in a bottom up manner by using a dp[n-1][2] array here dp[i][0] means that element is not selected and dp[i][1] means that element is selected (contributes to sum). So at every element we have to make two decisions (to take it or not obviously 
) but with the constraint that we canāt choose adjacent elements.
Therefore after initializing dp[first_elment][not selected] = 0 and dp[first element][selected]=first_element
There will be following cases after that
dp[current element][selected]=current_element+dp[prev element][not selected];
dp[current element][not selected]=max(dp[prev element][selected]+dp[prev element][not selected])
And then final ans will be base answer+max(dp[last element][selected], dp[last element][not selected])
My submission
2 Likes
very neat and clean code. CodeChef: Practical coding for everyone
must go through it. very easy to understand.
could someone give a testcase that led my solution to WA.
I am using greedy approach.
https://www.codechef.com/viewsolution/25456773
I wrote same code but used %d while printing ans 
Silly mistake
yes i got it, my approach of getting maximum sum is wrong, thanks
Very helpful. Though I didnāt really understand 4th point at first, but then I checked out
https://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/
Here is the python code:
I have tried solving the approach that you have shared. Iām not sure why am I getting WA. Iāve tried debugging it, Iām not able to identify the cases. Can you please help me ?
Hereās the code : CodeChef: Practical coding for everyone