Logic
Suppose the right-most position you go to is j. The problem breaks down into two problems, forward-score[j] = max score you can achieve from k to j. backward-score[j] = max score you can achieve from j to 1.
Code
#include <bits/stdc++.h>
using namespace std;
int n;
long dp[9999999];
long f[9999999];
long b[9999999];
long backwardscore(long a[],int j,int start);
long forwardscore(long a[],int k,int j);
long calvin(long a[],int k)
{ int maxi=-99999;
for(int j=k;j<=n-1;j++)
{
cout<<"j="<<j<<endl;
for(int i=0;i<n;i++)
{
f[i]=-1; b[i]=-1;
}
long h= forwardscore(a,k,j-1);
h=h+a[j];
cout<<"forwardscore"<<h<<endl;//k and j inclusive
long d=backwardscore(a,j,0);
cout<<"backward score "<<d<<endl;//j and 0 inclusive
long o=h+d-a[j]-a[k];
cout<<o<<endl;
if( o >maxi) maxi=o;
}
return maxi;
}
long forwardscore(long a[],int k,int j)
{
//index out of bounds
if(k>j) return 0;
if(f[k]!=-1) return f[k];
f[k]=max(a[k]+forwardscore(a,k+1,j),a[k]+forwardscore(a,k+2,j));
return f[k];
}
long backwardscore(long a[],int j,int start)
{
if(start<0) return 0;
if(b[j]!=-1) return b[j];
b[j]=max(a[j]+backwardscore(a,j-1,start),a[j]+backwardscore(a,j-2,start));
return b[j];
}
int main()
{
int k;
cin>>n>>k;
long a[n+1];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
f[i]=-1; b[i]=-1;
}
long g=calvin(a,k-1);
cout<<g<<endl;
return 0;
}