How to solve this "InfyTQ Hiring Test" Problem?

Revision en3, by HalfFragment, 2019-08-07 14:49:28

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.

Tags #dp, #graph theory, complexity optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English HalfFragment 2019-08-07 14:49:28 0 (published)
en2 English HalfFragment 2019-08-07 13:27:27 5 Tiny change: '0 -> 1 -> 3 -> 2' -> '0 -> 1 -> 2 -> 3 -> 2' (saved to drafts)
en1 English HalfFragment 2019-08-07 12:48:03 844 Initial revision (published)