[List] - Homework - Largest Increasing Subsequence
Здравейте, колеги!
Имам въпрос относно задачата от List & Matrices - Homework: * Largest Increasing Subsequence
С условие: Read a list of integers and find the longest increasing subsequence. If several such exist, print, the leftmost.
В Judge-a е на адрес: https://judge.softuni.bg/Contests/Practice/Index/173#11
Кодът, който съм написал е следният: http://pastebin.com/Lx4sJdjz
Дава ми само 70 точки.
Заложил съм и тестовите примери.
Усъмни ме нещо в единият от дадените примери (в слайд 34)
Examples:
Input: 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8
Output: 3 4 5 6 7 8 16
По каква логика, последното число от поредицата в изходът е 16 а не 9 ?
Не трябва ли последното число да бъде 9?
Съответно изходната редица: Output: 3 4 5 6 7 8 9
leftmost-поредицата не е ли при намиране на 2 или повече поредици с еднаква дължина, да се вземе най-лявата поредица, а не число от поредицата?
Така, както беше в подобното условие на задача: Max Sequence of Equal Elements (слайд 31)
(If several such exist, print the leftmost.)
Абсолютно същата е и последната част от условие и в тази задача?!
(If several such exist, print, the leftmost.)
Същото е. В случая дължината е еднаква и разликата е само в последния елемент. По-лявата редица е тази е по-ляв последен елемент.
Т.е. за поредици според условието се считат и следните:
Output: 3 4 5 6 7 8 16
и
Output: 3 4 5 6 7 8 9
а не само тази:
Output: 3 4 5 6 7 8 9
При вход: Input: 11 12 13 3 14 4 15 5 6 7 8 7 16 9 8