Problema
Um simulador de dados registra em uma lista cada lançamento de um dado de seis faces. Uma sequência é um grupo de lançamentos consecutivos com o mesmo valor; um lançamento sozinho é uma sequência de tamanho 1. Encontre a maior sequência. Se várias sequências empatarem no maior tamanho, informe a que começa primeiro.
Implemente longest_run_of_rolls(rolls).
Entrada
rolls: os lançamentos na ordem em que aconteceram, cada um de 1 a 6.
Saída
Retorne [start, length]: o índice (a partir de 0) em que a maior sequência começa e o tamanho dela. Para uma lista vazia, retorne [-1, 0].
Restrições
0 ≤ número de lançamentos ≤ 10 000
1 ≤ lançamento ≤ 6
Exemplos
Entrada:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]
Saída esperada:
expected = [4, 3]
Entrada:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};
Saída esperada:
std::vector<long long> expected = {4, 3};
Entrada:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};
Saída esperada:
long[] expected = new long[] {4, 3};
Explicação
Os três 6 que começam no índice 4 superam os dois 4: [4, 3].
Entrada:
rolls = [5, 5, 2, 2, 3]
Saída esperada:
expected = [0, 2]
Entrada:
std::vector<long long> rolls = {5, 5, 2, 2, 3};
Saída esperada:
std::vector<long long> expected = {0, 2};
Entrada:
long[] rolls = new long[] {5, 5, 2, 2, 3};
Saída esperada:
long[] expected = new long[] {0, 2};
Explicação
Os dois pares têm tamanho 2; os 5 começam primeiro, no índice 0: [0, 2].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Guarde onde a sequência atual começou.
Dica 2
Quando o valor mudar (ou a lista acabar), compare a sequência que terminou com a melhor até agora.
Dica 3
Só substitua a melhor quando a nova sequência for estritamente maior.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.