Поиск в последовательности чисел упорядоченной подпоследовательности макс длины

[Rusl92]

Здравствуйте, вы не могли бы рассказать про алгоритм
поиска в последовательности чисел упорядоченной подпоследовательности максимальной длины, который работает за n*log(n) действий

Заранее спасибо!

[LeBron]

Можно нормальную формулировку задачи?
Надо найти что? Строго возростающую или строго спадающую подпоследовательность максимальной длины? Или нестрого?
Чем не нравится обычный алгоритм для этой задачи (если я правильно понял, в чем сама задача)?

[Rusl92]

мне как раз таки нужен обычный алгоритм - можешь написать его

задача: в последовательности найти возрастающую подпоследовательность максимальной длины....

[Vago]

Алгоритм, говоришь...

#!/usr/bin/python
# -*- coding: cp1251 -*-
from numpy import *

def GetAscendingSeq( iS ):

    iF = iS+1
    while iF < n and a[iF] > a[iF-1]:
        iF += 1;

    return iF-1

a = array( [ 1, 2, 3, 2, 1, 2, 1, 0, 4, 5, 7 ] )

n = len( a )
iS = 0
iF = 0
lMax = 0

while ( iF < n ):
    iF = GetAscendingSeq( iS )
    if iF-iS+1 > lMax:
        iS0 = iS
        lMax = iF-iS+1

    iS = iF+1

print "The longest ascending sequence is starting from a[",iS0,"] =", a[iS0],
print "and is finishing with a[", iS0+lMax-1,"]=", a[iS0+lMax-1]

#

Не очень, кстати, понимаю, что и куда прилепить, чтобы логарифм в сложности появился. O(n) здесь, вроде...

[LeBron]

Сообщение от Vago

Алгоритм, говоришь...

#!/usr/bin/python
# -*- coding: cp1251 -*-
from numpy import *

def GetAscendingSeq( iS ):

    iF = iS+1
    while iF < n and a[iF] > a[iF-1]:
        iF += 1;

    return iF-1

a = array( [ 1, 2, 3, 2, 1, 2, 1, 0, 4, 5, 7 ] )

n = len( a )
iS = 0
iF = 0
lMax = 0

while ( iF < n ):
    iF = GetAscendingSeq( iS )
    if iF-iS+1 > lMax:
        iS0 = iS
        lMax = iF-iS+1

    iS = iF+1

print "The longest ascending sequence is starting from a[",iS0,"] =", a[iS0],
print "and is finishing with a[", iS0+lMax-1,"]=", a[iS0+lMax-1]

#

Не очень, кстати, понимаю, что и куда прилепить, чтобы логарифм в сложности появился. O(n) здесь, вроде...

Мы как бы о другом говорим... Почти во всех задачах подпоследовательность - это не просто "кусок" последовательности. Для Вашего примера ответ - подпоследовательность (1;2;3;4;5;7).

Вообще, самый простой способ - это стандартным алго (гугл в помощь) сначала найти максимальную возростающую, потом вторым проходом того же алго - максимальную спадающую. И взять максимум из 2 значений.

[loser]

Сообщение от LeBron

сначала найти максимальную возростающую, потом вторым проходом того же алго - максимальную спадающую. И взять максимум из 2 значений.

Проще все сделать за один проход, не?

[Vago]

Сообщение от LeBron

Мы как бы о другом говорим... Для Вашего примера ответ - подпоследовательность (1;2;3;4;5;7).

А-а... Тогда понятно, откуда такое требование на сложность Спасибо.