Let $$$A$$$ be an array of positive integers. Let you are playing a Game.
Initially your score is $$$0$$$.
Let you start from index $$$0$$$. In one move you can go from current cell $$$i$$$ to any adjacent cell i.e (either $$$i-1$$$ or $$$i+1$$$ if they exist). you can visit a cell any number of times. when you visit any cell $$$i$$$, then $$$A[i]$$$ is added in your score.
you should make exactly $$$k$$$ such moves.
what is the maximum possible value of score?

Example
if arr is $$$[7, 8, 7 ,9 , 5]$$$
and $$$k = 4$$$, then ans is $$$38$$$
i.e you can move like this : $$$0 - \gt 1 - \gt 3 - \gt 2$$$

Constraint:
$$$k \lt 10^6$$$
$$$N \lt 10^6$$$
$$$A[i] \lt 10^6$$$

The best i can think of it's $$$O(n*k)$$$ solution using dynamic programming, which definitely times out.