We can **probably** have dp[n + 1][x + 1], and do operations on that.

dp[i][j] denotes reaching the ith position, using j left moves.

The recurrence is dp[i][j] = max(dp[i - 1][j], dp[i + 1][j - 1]) + a[i]

**P.S: Take care of the base cases where j = 0, i = 0 etc**

As you can find out, the answer will be max(dp[k][0], dp[k - 2][1]....) until j \le x and i > 1 .

If you canâ€™t understand anything, donâ€™t hesitate to revert back.

shudnâ€™t the recurrence be dp[i][j]=max(dp[i-1][j-1],dp[i+1][j-1])+a[i]

bcz even if we go left it is considered as a move.

we can solve this using 2D dp and the dp state would be dp[N][z] , but there is one more thing mentioned in the problem , we canâ€™t make more than one consecutive move to left, so we can use 3D dp to handle it and dp state would be dp[N][z][2].

And each time we will move two options- >

1 -> move right

2-> move left , if last move was a right move

and take max of all the options.

At first i forgot about the condition that we r not allowed to make two consecutive moves to the left, but it still got accepted , may be due to weak test cases.

But here is the correct approach

Code: https://codeforces.com/contest/1389/submission/88413898

No thatâ€™s because there is no reason to move left more than once.

In fact you can prove the solution is of the form

`RRRR ...RLRLRLRL... RRRR`

Ohh

I just tried to make a counter testcase , but couldnâ€™t come up with one .

It seems like the soln is always of the form mentioned by u .Thanks for clearing it @everule1

https://codeforces.com/contest/1389/submission/88375463

See you require unique states to solve any dp problem, now in this, we need to keep track of which position we are at, how many moves to the left we have made, how many total moves are left, and if our last move was one to the left. Now this would lead to a complexity of n^2 because we are keeping track of how many moves are remaining and the position we are at.

If you observe carefully, in fact we donâ€™t need to memoize how many moves are remaining. That state can be recovered from other states i.e. the position we are at and how many moves weâ€™ve made to the left. Take a look at my recursive function, it will give you a better idea.

I guess you misunderstood the reply.

Over here x means the number of times we have already gone to the left.

Thus if we move to the left, we come at that (ith) index from (i + 1) index.

So, if we move to the left, dp[i][j] = dp[i + 1][j - 1] + a[i]

If we move to the right, we come from i - 1 index, and no left moves will be needed. So here, dp[i][j] = dp[i - 1][j] + a[i].

Combining the two equations,

dp[i][j] = max(dp[i + 1][j - 1], dp[i - 1][j]) + a[i] (as we need the maximum value)

I hope you could understand the recurrence @akash_lenka.

https://codeforces.com/contest/1389/submission/88825380

My solution if you have any trouble.

Geez, seeing all you 4 star coders slicing through DP problems like butter makes me wonder if I even belong in Div-1.

Believe me brother, I too think that

I think there is no hard need for DP.

i used prefix sum array to solve the problem.

```
ll n,k,z;
cin >> n >> k >> z;
ll a[n],pre_sum[n];
for (int i = 0; i < n; ++i)
{
cin >> a[i];
if(i==0) pre_sum[i] = a[i];
else pre_sum[i] = a[i]+pre_sum[i-1];
}
ll Max_sum=0,pair_sum=0,Min;
for (int i = 1; i <= k; ++i)
{
Min = min((k+1-i)/2,z);
pair_sum = a[i] + a[i-1];
Max_sum = max(Max_sum,(pre_sum[i-1] + pair_sum*Min + pre_sum[k-2*Min] - pre_sum[i-1]));
//cout << Max_sum << "\n";
}
cout << Max_sum << "\n";
```