Loading...
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

[Homework] Programming for Beginners - Lists and Matrices - Problem{11} - Largest Increasing Subsequence

Здравейте, колеги,

Моля някой от вас да публикува итеративно решение на задачата. Аз я реших с рекурсия, но не мога да измисля итеративен алгоритъм.

 

Условие:

Read a list of integers and find the longest increasing
subsequence. If several such exist, print, the leftmost.

Линк към Judge

 

Това е моето решение: http://pastebin.com/f38KV1Ek

Тагове:
0
Programming Basics 05/04/2016 16:34:48
ArmenPotourlyan+deleted!:
Отговор в предишна тема.
annsta avatar annsta 305 Точки
Best Answer

Тази задача е голямо предизвикателство! Моето собвено решение успя да покрие само 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 изцяло взаимства предложения алгоритъм.

 

0
05/04/2016 21:27:22
vancho avatar vancho 430 Точки

Аз не мога да си изясня условието. За мен според моя алгоритъм при примера: 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.

Като това също са последователни нарастващи и със същата дължина.

-1
05/04/2016 18:04:05
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

If several such exist, print, the leftmost.

0
05/04/2016 18:04:52
vancho avatar vancho 430 Точки

Да, вярно, благодаря!

-1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.