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.

  • 2
    $\begingroup$ Use dynamic programming. $\endgroup$ Oct 29, 2021 at 7:29
  • $\begingroup$ @YuvalFilmus: Wouldn't the dynamic programming approach take $O(n^2)$ too? $\endgroup$
    – Rob32409
    Oct 29, 2021 at 8:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – Steven
    Oct 29, 2021 at 9:15
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 29, 2021 at 10:41
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W.
    Oct 29, 2021 at 17:28

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.