Solução por Thiago Mota
Conhecimento prévio necessário:
Nós temos um vetor $$a_i$$ e temos que fazer todos os números deles virarem $$0$$ com o menor número de operações. A soma do vetor $$a_i$$ é $$0$$.
Nós podemos dividir o vetor em partes consecutivas de elementos com soma zero. Se a parte tem tamanho $$l$$ nós podemos usar todos os pares de vizinhos e transformar tudo em zero com $$l – 1$$ operações.
Então, a soma do número de operações em cada uma dessas partes gera uma resposta $$ans = n – k$$ onde $$k$$ é o número de partes. Então para minimizar a resposta temos que maximizar o número de partes.
Vamos calcular a soma de prefixos. Como as partes que nós procuramos tem soma zero, o prefixo no início e no final de cada uma será igual, logo podemos calcular a maior frequência entre todos os prefixos, a maior frequência será o número de partes que iremos dividir, logo a resposta é $$n – f$$ sendo $$f$$ a maior frequência. Segue o código: