Блог пользователя iMurat

Автор iMurat, история, 6 лет назад, По-русски

Дан массив 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
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

eewrd wwwrd qwerd qwwrd altqq

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Ну а если по сабжу — http://e-maxx.ru/algo/longest_increasing_subseq_log

    Возьми решение через дерево отрезков, сделай 2 дерева — одно для элементов, которые являются "верхом зубца", другое "низом зубца". Они пересчитываются друг через друга аналогично НПВ, только в одном случае ты берешь максимум на префиксе, в другом — на суффиксе.

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Очередь на максимум/минимум + бинпоиск по очереди. Для каждого числа бинпоиском ищем самую длинную зубчатую подпоследовательность когда оно является последним числом на возрастание/убывание и кладем результат в противоположную очередь (очередь на минимум/максимум здесь фактически является стеком).