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 -> 1 -> 3 -> 2$$$

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

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