# How to get the highest score in this game?

I would like some advice in this homework question. There is a three players game, in which each player ($$A, B$$, and $$C$$) is given a $$n$$-length array of integer values. There are $$n$$ rounds in this game. At every $$i$$-th round the players have to choose one value among $$A[i]$$, $$B[i]$$ and $$C[i]$$, which is going to be the score they will get in that round. Considering that the players cannot choose the same array consecutively, how should the players choose the optimal array combination that leads to the highest total score (sum of the scores they get at each round)?

So far I've come up with the solution of selecting at each round the highest possible value among $$A[i]$$, $$B[i]$$ and $$C[i]$$, but this takes $$O(n^2)$$. I also thought about setting the problem in matrix form to apply linear programming, something like $$\max_{x} \sum b_{i,j}(x)$$ such that $$Ax = b$$, where $$A$$ is a $$n\times 3$$ matrix (where the columns are the arrays $$A, B$$ and $$C$$), and $$x$$ is a $$3 \times n$$ matrix of 0's and 1's, but I'm not sure of this approach.

• Use dynamic programming. Oct 29, 2021 at 7:29
• @YuvalFilmus: Wouldn't the dynamic programming approach take $O(n^2)$ too? Oct 29, 2021 at 8:55
• How is the fact that there are three players relevant? From your description it seems that the choice of a player never interferes with the choices of the other players. Oct 29, 2021 at 9:15
• My guess at the problem is that you choose one of $A[i],B[i],C[i]$ at each turn, and cannot choose the same array consecutively. You want to maximize the sum of values. This can be solved in linear time using dynamic programming. Oct 29, 2021 at 10:41
• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
Oct 29, 2021 at 17:28

Let $$a_i$$, $$b_i$$, $$c_i$$ be the maximum number of points that you can get by picking A[i], B[i], C[i] in the last round.
Obviously $$a_1 = A$$, $$b_1 = B$$, $$c_1 = C$$.
And equally obvious is that $$a_i = A[i] + \max(b_{i-1}, c_{i-1})$$, $$b_i = B[i] + \max(a_{i-1}, c_{i-1})$$ and $$c_i = C[i] + \max(a_{i-1}, b_{i-1})$$. Just calculate each value in turn, then choose the largest of $$a_n$$, $$b_n$$ and $$c_n$$.
If you had not 3 arrays but k, this would run in $$O(n \cdot k^2)$$ if you do it in the obvious way, or $$O(n \cdot k)$$ if you are clever: You want the maximum of k values except value j, for each 1 ≤ j ≤ k. Just find the largest of all k values. That is also the maximum of (all but one values), unless you remove that value from your list, so one maximum needs to be recalculated.