Какой алгоритм использовать для этой задачи?

Question

[ConradToWin]

У меня есть задача:
"Вдоль аллеи растут деревья. Деревья имеют разную высоту. Для создания ландшафтного дизайна принять решение часть деревьев спилить и оставить только деревья, которые возрастают по высоте. Зная кол-во деревьев и высоту каждого дерева, необходимо определить наибольшее кол-во деревьев, которые возможно оставить. Например, если вдоль аллеи растет 9 деревьев и их высота равна: 5 8 3 2 6 4 5 3 7, то оставить, соблюдая необходимое условие, возможно только 4 дерева (3 4 5 7 или 2 4 5 7)."
И алгоритм/решение желательно на Python
P.S. Прошу прощения за вопрос плана "Сделайте всё за меня". Уже битый час сижу, думаю, но не могу даже понять за что зацепиться. Спасибо за внимание_

Answer 1

[Виталий Столяров]

https://e-maxx.ru/algo/longest_increasing_subseq_log

Comments

[ConradToWin]

Спасибо)

[Roman]

ConradToWin, Больше

[xmoonlight]

Roman, Спасибо за линк!

Answer 2

[longclaps]

Час - это много времени. За час можно пробежать полумарафон. Я не смогу, но чемпионы так могут.
Так и с этой задачей. Ты думаешь, что своим паршивым часом купил индульгенцию на подсказку? Пожалуйста: тебе нужно найти возрастающую подпоследовательность наибольшей длины. Можешь, например, взять первое дерево и продолжать подпоследовательность вправо. А затем взять первое еще не задействованое в подпоследовательностях дерево и продолжать подпоследовательность в обе стороны от него. И так далее. Так ты найдёшь наидлиннейшую подпоследовательность. Но я бы тебе посоветовал бросить - ты слабак.

Comments

[ConradToWin]

Огромное спасибо, теперь знаю от чего оттолкнуться)

[wataru]

longclaps, Вот только это жадное решение не обязательно найдет ответ. Контр пример:
100, 1, 2, 3, 101. Если взять первое дерево, то потом удастся добавить к нему только последнее. Но можно же взять все деревья после первого.

Правильное решение - динамическое программирование. Виталий Столяров привел отличную ссылку.

P.S. для дилетанта, дающего неправильные ответы, у тебя слишком много пафоса.

[longclaps]

wataru, ай-яй, ну, попробуем.

Можешь, например, взять первое дерево и продолжать подпоследовательность вправо

100, 101

А затем взять первое еще не задействованое в подпоследовательностях дерево

1

и продолжать подпоследовательность в обе стороны от него

1,2,3,101
Не переживай за меня, я в порядке.

зы Мне нравятся твои ответы, и эта оплошность меня не смущает. А неправедно плюсующим - фак.

[wataru]

longclaps,
Отлично, вот тебе чуть-чуть более сложный тест.
10 100 1 16 2 15 3 14 4

> Можешь, например, взять первое дерево и продолжать подпоследовательность вправо

10, затем взяли 100.

> А затем взять первое еще не задействованое в подпоследовательностях дерево
100
> и продолжать подпоследовательность в обе стороны от него
опять 10, 100

А правильный ответ тут - 1,2,3,4.
Какой бы ты алгоритм такого рода не придумал (они называются жадными алгоритмами, запиши куда-нибудь), я всегда смогу привести контр пример. В этой задаче можно так поставить числа, что ответом будет любое наперед заданное подмножество элементов.

Ты свое решение никак не исправишь, пока не доведешь его до полного перебора. Это, хоть и, очевидно, рабочее решение - оно никуда не годится. Как и твои ответы.

[longclaps]

wataru, фантазия на контрпримеры у тебя слабовата. Последняя четверка до конца будет незадействована, а затем

и продолжать подпоследовательность в обе стороны от него

4-3-2-1
Но всё же ты прав - жадный алгоритм тут не тянет.
А теперь знаешь что: иди в жопу. Ты же не дилетант, ты профи - вот там тебе и место. Адресок запиши куда-нибудь, чтобы не забыть.

[wataru]

longclaps, а каким раком из
"Можешь, например, взять первое дерево и продолжать подпоследовательность вправо. А затем взять первое еще не задействованое в подпоследовательностях дерево и продолжать подпоследовательность в обе стороны от него. И так далее. "
вообще берется 4? Или предлагается от каждого дерева начинать последовательность в обе стороны? Чем это решение не жадное?

Объясни дураку по шагам, как вот это решается?
1 16 2 15 1 3 14 1 4 5
Как твой алгоритм решает пропустить 10 100 в начале и единицы перед 3 и 4?

>А теперь знаешь что: иди в жопу.

Ты что, обиделся что ли? Ну ты и слабак! Не твое это дело - ответы на тостере писать, бросай это.

[longclaps]

wataru, жадное оно, жадное.
Дураку объясняю:

10 100 1 16 2 15 3 14 4

идучи слева направо, я до последнего не загребаю 4 - её экранирует 14. А дойдя до четверки, я действительно иду в обе стороны - так и написано в ответе, который ты так лихо раздраконил, а прочитать не удосужился.
Ладно, кончай в лужу пердеть, а то и в правду станешь профессионалом )

[wataru]

longclaps, нет уж позвольте, я еще не закончил с этой лужей!

А как в этом случае возьмется 1-2-3-4-5?

1 16 2 15 1 3 14 1 4 5

Почему берется не 1-4-5? Как ваш алгоритм решает пропустить 1, потом 14, потом взять 3, потом пропустить 1, 15, потом взять 2, пропустить 16 и взять 1?

жадное оно, жадное.

В этой задаче ни одна жадность работать не будет!

[longclaps]

wataru, отстань.

def greedy(l):
    best = []
    for i, a in enumerate(l):
        seed = [a]
        for j in range(i - 1, -1, -1):
            if l[j] < seed[-1]:
                seed.append(l[j])
        seed.reverse()
        for j in range(i + 1, len(l)):
            if seed[-1] < l[j]:
                seed.append(l[j])
        if len(best) < len(seed):
            best = seed
    return best


def deep(l):
    dp = [(0, -1, -1)]
    for i, a in enumerate(l, 1):
        j = max(range(i), key=lambda k: dp[k][0] if dp[k][1] < a else 0)
        dp.append((dp[j][0] + 1, a, j))
    _, a, j = max(dp)
    res = []
    while a != -1:
        res.append(a)
        _, a, j = dp[j]
    return res[::-1]


for s in '100 1 2 3 101\n10 100 1 16 2 15 3 14 4\n' \
         '1 16 2 15 1 3 14 1 4 5'.splitlines():
    l = list(map(int, s.split()))
    print(l, greedy(l), deep(l), '', sep='\n')

[wataru]

longclaps,

Ну, ты свой код-то вообще запускал?
На третьем тесте оно находит 1,2,15 вместо 1,2,3,4,5.

[100, 1, 2, 3, 101]
[1, 2, 3, 101]
[1, 2, 3, 101]

[10, 100, 1, 16, 2, 15, 3, 14, 4]
[1, 2, 3, 14]
[1, 2, 3, 14]

[1, 16, 2, 15, 1, 3, 14, 1, 4, 5]
[1, 2, 15]
[1, 2, 3, 4, 5]

В этой задаче жадность НЕ РАБОТАЕТ. Никак, вообще. Хоть слева направо ходи, хоть задом наперед, хоть через элемент. Если взять какой-то следующий элемент, то может отвалиться единственное правильное решение дальше, потому что текущий слишком большой, или слишком мелкий. И без знания всего элементов дальше ты никак не сможешь определить это.

[longclaps]

wataru, ты какой-то деревянный. Я тебе 2 часа назад сказал:

Но всё же ты прав - жадный алгоритм тут не тянет.

И указал на слабость твоего тогдашнего контрпримера. Ты, слава богу, смог его доработать, а я, чтобы закрыть тему, написал "отстань".