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

09.Largest Increasing Subsequence - Lists and Matrices - Exercises

Здравейте,

след двудневно дебъгване имам нужда от помощ по следната задача :D. Judge дава 83/100 точки (zero test #0 , test #2 , test #9 - Incorrect). Input-a на zero теста е редицата {7, 3, 5, 8, -1, 0, 6, 7}. Oчакваният output за най-дълга нарастваща подредица е  {3, 5, 6, 7}, а моят - {-1, 0, 6, 7}. В случая (а може би и в другите два incorrect) дължината на двете подредици е еднаква. Ще се радвам ако някой намери бъга в кода ми (http://pastebin.com/UTqpTXZj ) или даде hint къде е възможно да се намира.

L[0] -> 7 |  L[1] -> 3 |  L[2] -> 3 5 |  L[3] -> 3 5 8    [*Note : {3, 5, 6, 7} is missing]  |  L[4] -> -1  |  L[5] -> -1 0  |  L[6] -> -1 0 6  |  L[7] -> -1 0 6 7

са редиците, които алгоритъма, който ползвам извлича (въпросната от expected output-а липсва?).

Логиката ми е следната :

1) създаваме лист L от листове , подлистовете са всяка една нарастваща подредица 

2) първата подредица L[0] е винаги първия елемент на oригиналното множество от inputa (всяка подредица L[i] завършва с елемент D[i]

3) завъртаме цикъл от 1 , като на всяка стъпка създаваме нова подредица

4) проверяваме с вложен цикъл всяка една създадена подредица до сега, чиито последен елемент D[j] е по-малък от D[i]

5) избираме най-голямата, която отговаря на условие 4) , добавяме D[i] към края й и запазваме в текущата подредица

Source : https://www.youtube.com/watch?v=4fQJGoeW5VE&index=3&list=PLyRoUB6FODwkWN-eZXVPuhiKGqF9UIivS

1
Fundamentals Module 03/06/2016 00:14:38
kaloyannikov avatar kaloyannikov 531 Точки

[7, 3, 5, 8, -1, 0, 6, 7 ]

 стигнал си до ситуация листа ти е 3,5 следващия елемент е 8 добавяш го 

листа става [3,5,8] запзваш го някъде (примерно tempMaxList) но продължаваш да търсиш от ситуация [3,5] стигаш до [6] добавяш я и добавяш [7] и това ти става най-дългата поредица и изтриваш [3,5,8]. Не съм сигурен дали това е оптимално решение ,но мисля че така трябва да се получи.

EDIT : Като оптимизация може да се направи : пазиш индекса на числото където последно е спряла редицата, в случая това е -1. и продължаваш цикъла от там,но едва ли се налага в конкретния случай.

1
03/06/2016 01:00:03