Estou tentando resolver este problema algorítmico:

https://dunjudge.me/analysis/problems/469/

Por conveniência, resumi a declaração do problema abaixo.

Dada uma matriz de comprimento (<= 2.000.000) contendo números inteiros no intervalo [0, 1.000.000], encontre o maiorsubarray que contém um elemento majoritário.

Um elemento majoritário é definido como um elemento que ocorre> floor (n / 2) vezes em uma lista de comprimento n.

Limite de tempo: 1.5s

Por exemplo:

Se a matriz fornecida for [1, 2, 1, 2, 3, 2],

A resposta é 5 porque o sub-arranjo [2, 1, 2, 3, 2] de comprimento 5 da posição 1 a 5 (indexado 0) tem o número 2 que aparece 3> vezes o piso (5/2). Observe que não podemos pegar a matriz inteira porque 3 = floor (6/2).

Minha tentativa:

A primeira coisa que vem à mente é uma solução óbvia de força bruta (mas correta) que corrige os índices de início e fim de um subarray e o percorre para verificar se ele contém um elemento majoritário. Depois, tomamos o comprimento do subarray mais longo que contém um elemento majoritário. Isso funciona em O (n ^ 2) com uma pequena otimização. Claramente, isso não passará o prazo.

Eu também estava pensando em dividir os elementos em buckets que contêm seus índices em ordem classificada.

Usando o exemplo acima, esses buckets seriam:

1: 0, 2

2: 1, 3, 5

3: 4

Em seguida, para cada bloco, tentaria mesclar os índices para encontrar o subarray mais longo que contém k como o elemento majoritário, em que k é o rótulo inteiro desse bloco. Poderíamos então assumir o comprimento máximo sobre todos os valores de k. Não experimentei esta solução porque não sabia como executar a etapa de mesclagem.

Alguém poderia me aconselhar sobre uma abordagem melhor para resolver este problema?

Editar:

Resolvi esse problema graças às respostas de PhamTrung e hk6279. Embora eu tenha aceitado a resposta do PhamTrung porque ele sugeriu a idéia pela primeira vez, eualtamente recomendado olhando para a resposta de hk6279 porque sua resposta elabora a idéia do PhamTrung e é muito mais detalhada (e também vem com uma boa prova formal!).