3. Aktuálny zoznam prianí vzorové riešenie

3
3 1 2

3

6
3 1 4 1 5 9

5

Prvé pozorovanie

Hľadaná podpostupnosť je rastúca, teda sa v nej určite nemôžu nachádzať 2 rovnaké čísla. Keď skopírujem postupnosť niekoľkokrát za seba, nepridajú sa žiadne nové čísla. Teda hľadaná podpostupnosť môže mať dĺžku najviac počet rôznych čísel v pôvodnej postupnosti.

Konštrukcia

Rôznych čísel v pôvodnej postupnosti bude vždy najviac \(n\), teda aj najväčší možný výsledok bude tiež \(n\). Potom môžeme každé z čísel z výslednej podpostupnosti brať z inej kópie pôvodného zoznamu. Možné optimálne riešenie môžeme dostať napríklad tak, že si rôzne čísla nachádzajúce sa v zozname usporiadame od najmenšieho po najväčšie. Toto bude najdlhšia neklesajúca podpostupnosť skopírovaného zoznamu a získať ju môžeme napríklad tak, že prvý prvok zoberieme z prvej kópie zoznamu, druhý z druhej atď.

Ako to naprogramovať?

Keďže nám stačí zistiť len dĺžku najdlhšej rastúcej podpostupnosti, stačí len nájsť počet rôznych čísel, ktoré sa nachádzajú na vstupe. Keď si čísla v pôvodnom zozname utriedime, rovnaké čísla sa budú nachádzať vedľa seba, teda pomocou jedného for cyklu vieme zistiť počet rôznych čísel v zozname. Toto riešenie má časovú zložitosť \(O(n \log_{2}{n})\). Takéto riešenie naprogramované v Pythone by mohlo vyzerať napríklad takto:

n = int(input())
cisla = list(map(int,input().split())) # načítanie vstupu

cisla.sort() # usporiadam si čísla, nech sú rovnaké pri sebe
vysledok = 0;

for i in range(1,n): # zistím počet rôznych čísel
    if(cisla[i-1] != cisla[i]):
        vysledok += 1;

vysledok += 1 # treba ešte pripočítať posledné číslo

print(vysledok)

Druhá možnosť je využiť knižničnú dátovú štruktúru set. Set si vieme predstaviť ako množinu, v ktorej sa každý prvok môže nachádzať najviac raz. Do tejto množiny vieme vložiť nejaký prvok, odstrániť z nej nejaký prvok alebo zistiť, či sa v nej nachádza nejaký prvok, všetko v čase \(O(\log_{2}{n})\). Rozdiel medzi dátovými štruktúrami set a unordered set je ten, že prvky v sete sú usporiadané, teda ich vieme prechádzať od najmenšieho po najväčší. Preto má unordered set lepšie časové zložitosti a to \(O(1)\) pre pridávanie, odstránenie aj zistenie, či sa prvok nachádza v množine.

Keďže v sete sa každé číslo nachádza len raz, stačí nám len každé číslo doň v čase \(O(\log_{2}{n})\) (alebo \(O(1)\) v prípade unordered set) pridať a potom vypísať veľkosť tohto setu. Toto riešenie má časovú zložitosť \(O(n \log_{2}{n})\) pri použití dátovej štruktúry set (alebo \(O(n)\) pri použití štruktúry unordered set), lebo každé číslo na vstupe treba do setu pridať práve raz. Takéto riešenie v C++ by mohlo vyzerať napríklad takto:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,cislo;
    cin >> n;
    
    set<int> cisla;
    
    for(int i = 0;i < n;i++){
        cin >> cislo;
        cisla.insert(cislo);
    }
    
    // keďže v set nemôže obsahovať rovnaké čísla,
    // veľkosť setu čísla bude počet rôznych čísel na vstupe
    cout << cisla.size() << endl; 
}

Pamäťová zložitosť je v oboch prípadoch \(O(n)\), lebo si stačí pamätať len čísla z pôvodného zoznamu.