Cerință
Dintr-un șir de n numere alegi poziții în ordine strict crescătoare, astfel încât valorile selectate să fie strict crescătoare. Mai întâi se consideră lungimea maximă posibilă a unui asemenea subșir. Determină câte alegeri de poziții ating această lungime.
Date de intrare
Se citește n, apoi cele n valori, în ordinea lor din șir.
Date de ieșire
Afișează un singur număr întreg: numărul subșirurilor strict crescătoare de lungime maximă, nu lungimea lor. Rezultatul se afișează exact, fără modulo. Alegerile de poziții diferite se numără separat, inclusiv atunci când produc aceleași valori.
Restricții
1 ≤ n ≤ 12; 1 ≤ fiecare valoare ≤ 10. Pozițiile selectate nu trebuie să fie consecutive. Două valori egale nu pot urma una după alta într-un subșir strict crescător.
Explicație
Pentru șirul 2,1,4,2,3, lungimea maximă este 3. Singura alegere de poziții care o atinge este (2,4,5), cu valorile 1,2,3, deci răspunsul este 1. În al doilea exemplu există un singur element și un singur subșir de lungime maximă.
Observații
Selecție Algo25 pentru pregătirea interviurilor: programare dinamică.
Reper tematic pentru pregătire: https://www.hackerrank.com/interview/interview-preparation-kit
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Alegerea unor poziții nu cere ca ele să fie consecutive. Pentru un subșir, ordinea inițială se păstrează.Mărește schema ↗Date de intrare
5
2 1 4 2 3
Date de ieșire
1
Exemplul 2
Date de intrare
1
1
Date de ieșire
1
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →