How to get the highest score in this game?

Question

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.

Answer 1

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[1]$, $b_1 = B[1]$, $c_1 = C[1]$.

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.