Динамика за O(nlogn)

Правка ru1, от iMurat, 2019-01-07 07:03:48

Дан массив a состоящий из n целых чисел. Найти длину самой длинной зубчатой подпоследовательности. Зубчатой подпоследовательностью будем назвать такую подпоследовательность, где выполняется одно из следующих условий: a[i] > a [i+1] < a[i+2]>...<a[j] или a[i] < a[i+1] > a[i+2] < ... > a[j], 1 <= i <= j <= n. Ограничения: -10000 <= a[i] <= 10000, и 1 <= n <= 10^5 Вот мое решение за O(n^2), как решить за O(nlogn)?

Code
Теги дп

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский iMurat 2019-01-07 07:03:48 1731 Первая редакция (опубликовано)