I have been trying to solve Calvins Game problem, but I am getting wrong ans and I am not able to figure out what is wrong in my logic.

Fine i am posting this since answers are available on the internet and there s no rules for this contest as such and there s no reply for my previous query.

``````n,k=map(int,input().split())
a=list(map(int,input().split()))
arr=[-999999999999999]*n
k-=1
if(k+1<n):
arr[k+1]=a[k+1]
if(k+2<n):
arr[k+2]=max(a[k+2],arr[k+1]+a[k+2])
for i in range(k+3,n):
arr[i]=max(arr[i],arr[i-2]+a[i],arr[i-1]+a[i])
arr[n-2]=max(arr[n-1]+a[n-2],arr[n-2])
for i in range(n-3,k,-1):
arr[i]=max(arr[i],arr[i+2]+a[i],arr[i+1]+a[i])
if(k==n-1):
arr[n-2]=a[n-2]
arr[n-1]=0
if(k==n-2):
arr[n-1]=a[n-1]
arr[n-2]=max(0,arr[n-1]+a[n-2])
if(arr[k]<0):
arr[k]=0
for i in range(min(k,n-3),-1,-1):
arr[i]=max(arr[i],arr[i+2]+a[i],arr[i+1]+a[i])
print(arr)
``````

Use simple DP. Initialize arr with all minimum values. Then find the arr[i] represents the maximum value of reaching that position . First run from k to n.Then come back from n to 1. And arr[i] is arr[i]=max(arr[i],arr[i-2]+a[i],arr[i-1]+a[i]) while going front and arr[i]=max(arr[i],arr[i+2]+a[i],arr[i+1]+a[i]) while coming back from n-1.Special conditions for arr[n-1] and arr[n-2] have been given to avoid SEGMENTATION fault. Furthermore while coming back if arr[k]<0 no need to traverse right at all you can go left starting itself, so set arr[k]=0.

1 Like

@anirudhjarvis
It would be better if you can tell me what is wrong with my code.

@anirudhjarvis

5 1
5 3 -2 -1 -1

For this input output should be 10 but ur program prints output as 8.
as go from 1 to 2 to 4 to 2 to 1. ANSWER = 10 not 8. FOLLOW MY PREVIOUS ANSWER DP APPROACH U’LL CORRECT UR ERROR.Essentially both LOGIC IS SAME just see my code and tweak ur code as ur DP is slightly wrong.(You should not traverse just from maxscore, traverse from back totally like me.See my code,approach and do it.)