CMI 2026 | CS | Part C | Question: 4

Question

In the Pots-of-Gold game, there is a row of $n$ pots $P_{1}, \ldots, P_{n}$. Each pot contains some number of gold coins. You remove pots and collect the gold coins from the pots that you remove, subject to the rules below. Your aim is to collect as many gold coins as possible.

• You start with no gold coins and remove pots one at a time. You can remove any pot that is available for removal.
• In the beginning, all pots are available for removal. Removing pot $P_{i}$ makes the pots $P_{i-1}$ and $P_{i+1}$ (if they exist) permanently unavailable.

1. Assuming that we have an array $G[1 \ldots n]$ with $G[i]$ storing the number of gold coins in pot $P_{i}$, devise an algorithm $\operatorname{PotsOfGold}(G, n)$ that computes the maximum number of gold coins that you can collect. Your algorithm should run in $O(n)$ time in the worst case. You can assume that each arithmetic operation involving two integers, and each array access (reading/writing one element) takes constant time. Hint: Use dynamic programming.
2. Clearly explain why your procedure of part (a) correctly computes the required output.
3. Explain why your procedure of part (a) runs in $O(n)$ time in the worst case.