Maximum number of multiples of an array element preceding it Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$.

For example, given the array


  36 40 16 24 27 12 9 4


We see that element 4 has the highest number of multiples (5) as per the given conditions, so the answer is 5.

My approach: I used brute force to solve this. I used nested loops to solve this. The first loop from the last element and the second loop from the first element to the second to last element.

Can you help me improve the running time?
Hint: note that if there are duplicates, we are basically only interested in the last occurrence of each value. Now if you maintain an array $C$ of size $\max_i A[i]$ such that at the $i$-th iteration of your algorithm $C_k=|\{j\le i, A_j=k\}|$, how can you compute the number of multiples of $A[i]$ to the left of $i$ so that the overall complexity is not too high?