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