Faça um programa que encontre o conjunto de 5 dígitos consecutivos na sequência abaixo que gere o maior produto:
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Passo 1

O enunciado pede pra gente achar, numa sequência de 1000 dígitos, qual janela de 5 dígitos consecutivos produz o maior produto quando multiplicados. O conteúdo aqui é varredura (sliding window) e cálculo de produto de algarismos. Vamos precisar converter cada caractere em inteiro e testar todas as posições possível.

Passo 2

Primeiro a gente limpa a sequência: remove quebras de linha e espaços pra obter uma string única com 1000 caracteres, cada um um dígito de ‘0’ a ‘9’.

Passo 3

Daí usamos uma janela deslizante de tamanho 5: para cada posição i de 0 até 1000-5, extraímos os 5 caracteres seq[i:i+5] e convertê-los em dígitos inteiros.

Passo 4

Em cada janela, calculamos o produto dos cinco dígitos. Em termos de fórmula, se a janela em i tem dígitos di,di+1,di+2,di+3,di+4, fazemos
Pi = di cdot di+1 cdot di+2 cdot di+3 cdot di+4
e comparamos com o maior produto já encontrado.

Passo 5

Vamos manter duas variáveis: uma para o maior produto e outra para a sequência de 5 dígitos que gerou esse produto. A cada novo Pi, se ele for maior, atualizamos essas variáveis.

Passo 6

Ao final do laço, descobrimos que a maior sequência de 5 dígitos é ‘99879’, pois
9 cdot 9 cdot 8 cdot 7 cdot 9 = 40824
que é o maior produto possível para qualquer janela de cinco dígitos na sequência dada.

Resposta

99879

Exercícios relacionados