Өсөх Дэд Дараалал

2s

512MB

1332

0%

Dynamic Programming

$n$ бүхэл тоо бүхий массив өгөгдөнө. Массивын хамгийн урт өсөх дэд дарааллыг ол, өөрөөр хэлбэл элемент бүр өмнөхөөсөө их байх хамгийн урт дэд дарааллыг.

Дэд дараалал гэдэг нь зарим элементийг нь хасаж, үлдсэн элементүүдийн дарааллыг өөрчлөхгүйгөөр массиваас үүсгэсэн дараалал юм.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд массивын хэмжээ $n$ бүхэл тоо байна.

Дараагийн мөрөнд массивын утгууд $x_1,x_2,\ldots,x_n$ $n$ бүхэл тоо байна.

Гаралтын формат

Хамгийн урт өсөх дэд дарааллын уртыг хэвлэ.

Хязгаарлалт

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Жишээ

Оролт1

8
7 3 5 3 6 2 9 8

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...