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 2 - \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.
It seems optimal to me to stay at some point and alternate between $$$(i, i+1)$$$. So try every such point and calculate the score to go there (prefix sum) and stay there (simple multiplication) in $$$O(1)$$$.
In your example, the moves should be $$$0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2$$$, right? So here it is optimal to stay at $$$(2, 3)$$$.
How can i prove this greedy strategy?
Take any sequence of moves. Look at the pair of adjacent squares in that sequence that has the highest sum. You can show that it if we start alternating between these squares instead of moving away, we get a better sequence. You can also show that if we take the shortest possible path to them, we get a better sequence. Thus any optimal sequence must have this form: moving to some point as fast as possible and alternating there.
Auto comment: topic has been updated by HalfFragment (previous revision, new revision, compare).
Could you give a link to the problem?
This is problem from hiring challenge on "Hackerrank", and they do not make problem accessible after test.