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.
Here is the link to my code, please help.
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[0])
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.
for codes visit:-THIS LINK
PLEASE UPVOTE AND FOLLOW FOR ANY QUERIES IF U FIND IT HELPFUL.
1 Like
Its not loading in pastebin. Send me the link in ideone.
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.)
PLEASE UPVOTE MY ANSWER AND ACCEPT IT AND FOLLOW FOR ANY QUERIES IF U FIND IT HELPFUL.