HalfFragment's blog

By HalfFragment, history, 5 years ago, In English

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 -> 2 -> 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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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)$$$.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    How can i prove this greedy strategy?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by HalfFragment (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you give a link to the problem?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is problem from hiring challenge on "Hackerrank", and they do not make problem accessible after test.