Algoritmul, pas cu pas
Gândește-te la fiecare număr nu ca la o valoare, ci doar prin forța lui — câți divizori are. Imediat ce am eticheta asta pentru fiecare element, ambele cerințe devin niște întrebări simple despre o listă de etichete:
- C1 — vreau eticheta (forța) cea mai mare; dacă mai multe numere o ating, îl aleg pe cel mai mic ca valoare.
- C2 — „rearanjarea convenabilă” înseamnă că pot aduce unul lângă altul orice numere vreau, deci cea mai lungă secvență cu aceeași forță e pur și simplu grupul cu eticheta cea mai des întâlnită.
Toată dificultatea reală e să calculez forțele repede: numerele merg până la și sunt până la , așa că nu pot număra divizori unul câte unul de la la .