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

1.пускаш един цикъл за целия масив 

2.в него пускаш още един такъв самоче от ако в първия си с i  до i +1 до дължината на масива

3.вътре сръвняваш числата или ги печаташ или почваш отначало да ги сръвняваш.

по късно ще ти линкна и код

-1
sevgin0954 avatar sevgin0954 556 Точки

Не виждам как ще работи за непоследо­вателни числа.sad

0
spzvtbg avatar spzvtbg 582 Точки

но в примерния масив горе , най  дълга нарастваща поредица може да е и 

2 4 5 8     освен    2 4 6 8   или трябва да е първата най дълга поредица.

0
sevgin0954 avatar sevgin0954 556 Точки

Първата.

0
30/04/2017 15:58:14
sevgin0954 avatar sevgin0954 556 Точки

Има ли начин да се реши само с материала до масиви от книгата?Има и някакво обяснение но нищо не разбрах от негоsmiley

Задачата може да се реши с два вложени цикъла и допълнителен масив len[0..n-1]. Нека в стойността len[i]пазим дължината на най-дългата нарастваща подредица, която започва някъде в масива (не е важно къде) и завършва с елемента arr[i]. Тогава len[0]=1, a len[x] е максималната сума max(1+len[prev]), където prev<x иarr[prev]<arr[x]. Следвайки дефиницията len[0..n-1] може да се пресметне с два вложени цикъла по следния начин: първият цикъл обхожда масива последователно отляво надясно с водеща променлива x. Вторият цикъл (който е вложен в първия) обхожда масива от началото до позиция x-1 и търси елемент prev с максимална стойност на len[prev], за който arr[prev]<arr[x]. След приключване на търсенето len[x] се инициализира с 1 + най-голямата намерена стойност на len[prev]или с 1, ако такава не е намерена.

Описаният алгоритъм намира дължините на всички максимални нарастващи подредици, завършващи във всеки негов елемент. Най-голямата от тези стойности е дължината на най-дългата нарастваща подредица. Ако трябва да намерим самите елементи съставящи тази максимална нарастваща подредица, можем да започнем от елемента, в който тя завършва (нека той е на индекс x), да го отпечатаме и да търсим предходния елемент (prev). За него е в сила, че prev<x и len[x]=1+len[prev]. Така намирайки и отпечатвайки предходния елемент докато има такъв, можем да намерим елементите съставящи най-дългата нарастваща подредица в обратен ред (от последния към първия).

0
28/03/2017 18:59:56