Софтуерно Инженерство
Loading...
sholeto avatar sholeto 93 Точки

List and Matrices: Largest Increasing Subsequence - Неразбрано условие/пример.

Като ментор съм сигурен, че ще получа доста въпроси за последните задачи от тази лекция, затова предварително искам да изясня тази задача. Става въпрос за тази презентация: https://softuni.bg/downloads/svn/programming-basics/Jan-2016/Part-II-Programming-for-Beginners/3.%20Lists-and-Matrices.pptx

Относно задачата на слайд 34. Largest Increasing Subsequence

 

Условието и примера са следните:

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

Input | Output
1 | 1
7 3 5 8 -1 6 7 | 3 5 6 7
1 2 3 3 4 5 | 1 2 3
1 2 3 3 4 5 5 6 7 8 | 5 6 7 8
11 12 13 3 14 4 15 5 6 7 8 7 16 9 8   | 3 4 5 6 7 8 9

Ако разбирам правилно условието, бих казал, че изхода трябва да е такъв:

Input | Output
1 | 1
7 3 5 8 -1 6 7 | 3 5 6 7
1 2 3 3 4 5 | 1 2 3 4 5
1 2 3 3 4 5 5 6 7 8 | 1 2 3 4 5 6 7 8
11 12 13 3 14 4 15 5 6 7 8 7 16 9 8   | 3 4 5 6 7 8 16

 

Търсим най-голямото нарастващо подмножество. Алгоритъма, който съм използвал преди, когато решавах подобна домашна, ми дава резултатите по-горе, които мисля, че са правилни за даденото условие. Разбира се, преправих го да намира най-дългото нарастващо подмножество, а не най-дългото ненамаляващо подмножество, както беше в моята домашна. Я кажете аз ли не разбирам правилно нещата, или примерите на слайда са сгрешени? Все пак мисля да докладвам за грешка в инстанцията на курса, и този доклад да не стане по моя грешка. :)

 

Edit: На последния пример трябва да е 3 4 5 6 7 8 16, а не 3 4 5 6 7 8 9 както писах първо.

0
Programming Basics 26/03/2016 10:57:48
nakov avatar nakov SoftUni Team Trainer 5296 Точки
Best Answer

Здравейте, оправихме грешката. Вече има вярно условие на сайта + коректни тестове в judge системата: https://judge.softuni.bg/Contests/Practice/Index/173#11.

Задачата се решава с програмна техника наречена "динамично оптимиране". Не случайно е със звездичка (само за шампиони). Подробно обяснение как се решава задачата + постъпково описано решение (лаб) има в курса по алгоритми, в темата "Dynamic Programming": https://softuni.bg/trainings/1194/algorithms-september-2015.

Успех с тази задачка. Предупреждавам, че не е много лесна.

Наков

4