Здравейте, колеги,
Моля някой от вас да публикува итеративно решение на задачата. Аз я реших с рекурсия, но не мога да измисля итеративен алгоритъм.
Условие:
Read a list of integers and find the longest increasing
subsequence. If several such exist, print, the leftmost.
Това е моето решение: http://pastebin.com/f38KV1Ek
Тази задача е голямо предизвикателство! Моето собвено решение успя да покрие само 50/100 от тестовете в Judge, а на останалите получих индикация за memory limit :) Но в предишна тема за тази задача https://softuni.bg/forum/8855/list-and-matrices-largest-increasing-subsequence-nerazbrano-uslovie-primer#answer-25261 има подробна информация за решаването й с алгоритъм, който използва dynamic programming. Това решение https://gist.github.com/astambi/98f920074883963ef3f1b8b780024cf6 изцяло взаимства предложения алгоритъм.
Аз не мога да си изясня условието. За мен според моя алгоритъм при примера: 1 2 5 3 5 2 4 1 -> отг. е 1 2 3 5, за защо не: 1 2 3 4
Както и тук: 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8 -> отг. е 3 4 5 6 7 8 16, за защо не: 3 4 5 6 7 8 9.
Като това също са последователни нарастващи и със същата дължина.
If several such exist, print, the leftmost.
Да, вярно, благодаря!