Let $A$ be an array of positive integers. Let you are playing a Game.<br>↵
Initially your score is $0$. <br>↵
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. <br>↵
you should make exactly $k$ such moves. <br>↵
what is the maximum possible value of score?<br><br>↵
↵
<b>Example</b><br>↵
if arr is $[7, 8, 7 ,9 , 5]$ <br>↵
and $k = 4$, then ans is $38$<br>↵
i.e you can move like this : $0 -> 1 -> 2 -> 3 -> 2$<br><br>↵
↵
<b>Constraint</b>:<br>↵
$k < 10^6$<br>↵
$N < 10^6$<br>↵
$A[i] < 10^6$<br><br>↵
↵
The best i can think of it's $O(n*k)$ solution using dynamic programming, which definitely times out.
Initially your score is $0$. <br>↵
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. <br>↵
you should make exactly $k$ such moves. <br>↵
what is the maximum possible value of score?<br><br>↵
↵
<b>Example</b><br>↵
if arr is $[7, 8, 7 ,9 , 5]$ <br>↵
and $k = 4$, then ans is $38$<br>↵
i.e you can move like this : $0 -> 1 -> 2 -> 3 -> 2$<br><br>↵
↵
<b>Constraint</b>:<br>↵
$k < 10^6$<br>↵
$N < 10^6$<br>↵
$A[i] < 10^6$<br><br>↵
↵
The best i can think of it's $O(n*k)$ solution using dynamic programming, which definitely times out.
