Solução escrita por Caique Paiva
Conhecimentos Prévios Necessários:
Primeiro, veja que maximizar a quantidade de bolas retiradas é a mesma coisa que minimizar a quantidade de bolas que sobram. Então, seja $$[a, c], [b, d]$$ dois intervalos em que fizemos as operações, então, $$a < b < c < d$$ é falso, pois, suponha sem perda de generalidade que fazemos a operação em $$[a, c]$$ primeiro, então, não podemos fazer a operação $$[b, d]$$, pois $$a_b$$ já não está no vetor mais. Além disso, se $$[b, d]$$ estiver contido em $$[a, c]$$, então, só precisamos fazer a operação $$[a, c]$$. Portanto, podemos supor que qualquer sequência de operações tem intervalos disjuntos.
Defina $$dp_i$$ para ser a quantidade mínima de bolas que conseguimos deixar quando olhamos somente para o subarray $$a_1, a_2, \cdots a_i$$, em particular, $$dp_0 = 0$$. Vamos calcular $$dp_{i+1}$$ em função das dp’s menores.
Primeiro, olhando para o subarray $$a_1, a_2, \cdots , a_{i+1}$$, se não removemos a bola $$i+1$$, então a menor quantidade de bolas que conseguimos ter é $$dp_i +1$$, pois não removemos a bola $$i+1$$, então nós só olhamos para o array $$a_1, \cdots a_i$$ para fazer as operações, que nós sabemos que conseguimos deixar no mínimo $$dp_i$$ bolas nele.
Agora, se nós removermos a bola $$i+1$$ com a bola $$j$$, então removemos todas as bolas no intervalo $$[j, i+1]$$, ou seja, sobrou o array $$a_1, a_2, \cdots a_{j-1}$$, que conseguimos deixar no mínimo $$dp_{j-1}$$ bolas.
Então, veja que esses dois casos abrange todos os casos possíveis, logo
$$dp_{i+1} = min(dp_{i}+1, min \{ dp_j | a_{j+1} = a_{i+1}, j+1 < i \} )$$
Perfeito, sabemos calcular a $$dp_n$$ e nossa resposta vai ser $$n – dp_n$$. Só temos um problema, para calcular essa dp, quando estamos no estado $$i$$, nós percorremos por $$dp_1, dp_2, \cdots , dp_{i-1}$$ no pior dos casos, ou seja, a transição da i-ésima posição da dp é $$O(i)$$. Como temos $$n$$ valores para calcular, a complexidade total é $$O(1+2+\cdots + n) = O(n^2)$$, que não passa com as constantes do problema :(.
Como podemos corrigir isso? Veja que $$1 \le a_i \le n$$, então, vamos criar outro vetor chamado $$m[n+1]$$, inicializado com $$m_i = inf$$ para todo $$i$$, e vamos calcular a dp de forma iterativa. Então, quando estamos calculando $$dp_{i+1}$$, o vetor $$m$$ guarda, para todo $$a_x$$, com $$x \le i$$, qual é o $$j$$ onde $$dp_j$$ é minimizado e $$a_{j+1} = a_x$$, então
$$dp_{i+1} = min(dp_i +1, m[a_{i+1}])$$
E, para atualizar $$m$$ depois de cada operação, basta fazer $$m[a_{i+1}] = min(m[a_{i+1}], dp_i)$$. Com essa otimização, a transição da $$dp$$ está sendo realizada em $$O(1)$$, logo calculamos a $$dp$$ toda em $$O(n)$$, que passa nas constantes do problema.
Clique aqui para ver o código