# O(n) time algorithm for maximum earnings

There are $n$ plates $p_1$ to $p_n$ each filled with money of value $a_1$ to $a_n$. You can take the money from one or more plates if the sum of the money in them is divisible by three. I need a $\mathcal{O} (n)$ asymptotic time logarithm for finding the maximum earnings that can be achieved. I have no idea for such a fast algorithm, so any help is welcomed.

• Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. – Raphael Aug 25 '15 at 14:11

You can use DP for solving this problem.

Let's iterate $i$ from $1$ to $n$ and calculate next values for each $i$:

1. $m_{i,0}$ - biggest sum of money from plates $j \le i$ which is divisible by 3
2. $m_{i,1}$ - biggest sum of money from plates $j \le i$ which have reminder 1 after division by 3
3. $m_{i,2}$ - biggest sum of money from plates $j \le i$ which have reminder 2 after division by 3

Base case: $m_{0,0} = 0, m_{0,1} = -\infty, m_{0,2} = -\infty$

Iteration:

1. $k \in [0, 1, 2]: m_{i, k} = m_{i-1, k}$
2. $k \in [0, 1, 2], m_{i-1,k} \ne -\infty: m_{i, (m_{i-1,k} + a_i)\%3} = max(m_{i, (m_{i-1,k} + a_i)\%3}, m_{i-1,k} + a_i)$

And result will be $m_{n,0}$.

• That sure isn't easy to figure out. Well done my friend :) – user3719857 Aug 25 '15 at 10:55
• And why would this be correct? – Raphael Aug 25 '15 at 14:10
• Please consider not to encourage undesirable posting behaviour. – D.W. Aug 25 '15 at 16:39