TheKFactor

Bob has been selected to compete on a game show called The K Factor. The rules are as follows: The game is played on a strip of N cells that goes from the left to the right. The cells are numbered from 0 to N-1, starting on the left end. Additionally, each cell of the grid has a value written on it. You are given these values in the int[] values. Bob starts the game on cell 0. During the game he will sometimes be asked to make a move. Each time he is asked to do so, he has two options: he can either end the whole game (remaining where he stands at that moment), or move one cell to the right. The amount he wins is the value written in the cell where he stands at the end of the game. Of course, there is a catch. At the beginning of the game, the host of the show generates a secret integer K. The value of K is always between 0 and N-1, inclusive. K is then used as the maximum number of times the host will ask Bob to make a move. (If Bob actually makes K moves to the right without deciding to end the game, after Bob's K-th move the host will terminate the game. In this case Bob still gets the amount written in the cell where he finished the game.)

The host of the show keeps the value of K secret from Bob. However, Bob does have some information about K. He knows that K is chosen at random. He does not know the exact probability distribution used by the host when generating K, but he knows one property of this probability distribution: for each positive integer X, the chance that K is less than X is at most X/N.

Assume that Bob uses the strategy that maximizes the expected value of the amount he wins against the worst possible distribution of values for K. By a "strategy", we mean that Bob selects, for each cell, the probability that he will stop at that cell if he reaches it. Please find the expected value of the amount Bob will win.