SPOJ PROBLEM 14930: PRINCESS FARIDA (FARIDA)

Easy DP problem!!!

The problem states that it will either accept coins from ith mobnster or leave it...........
It will accept if previous sum was less than the sum of adding coins to previous to previous
sum of coins..........

 Consider dp[n] array for storing no. of coins till ith position(0-based)

So,     dp[0]=arr[0]   //no other option but just to consider it
         dp[1]=max(dp[0],arr[1])
         dp[2]=max(dp[1],arr[2]+dp[0])
         dp[3]=max(dp[2],arr[3]+dp[1])
         .
         .
         .
         dp[i]=max(dp[i-1],arr[i]+dp[i-2])

Testcase#1:
1 3 6 4 5                     
dp[0]=1
dp[1]=3
dp[2]=7
dp[3]=7
dp[4]=12

Answer is: 12

Testcase#2:
1 2 3 4 5
dp[0]=1
dp[1]=2
dp[2]=4
dp[3]=6
dp[4]=9

Answer is: 9