Масиви - Задача 6 от книгата c#
Напишете програма, която намира максималната подредица от нарастващи елементи в масив arr[n]. Елементите може и да не са последователни. Пример: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} - {2, 4, 6, 8}. ?
Напишете програма, която намира максималната подредица от нарастващи елементи в масив arr[n]. Елементите може и да не са последователни. Пример: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} - {2, 4, 6, 8}. ?
1.пускаш един цикъл за целия масив
2.в него пускаш още един такъв самоче от ако в първия си с i до i +1 до дължината на масива
3.вътре сръвняваш числата или ги печаташ или почваш отначало да ги сръвняваш.
по късно ще ти линкна и код
Не виждам как ще работи за непоследователни числа.![sad sad](https://softuni.bg/Scripts/ckeditor/plugins/smiley/images/sad_smile.png)
https://www.hackerrank.com/challenges/longest-increasing-subsequent
Тази задача е от алгоритми и се решава с динамично оптимиране
но в примерния масив горе , най дълга нарастваща поредица може да е и
2 4 5 8 освен 2 4 6 8 или трябва да е първата най дълга поредица.
Първата.
Има ли начин да се реши само с материала до масиви от книгата?Има и някакво обяснение но нищо не разбрах от него![smiley smiley](https://softuni.bg/Scripts/ckeditor/plugins/smiley/images/regular_smile.png)
Задачата може да се реши с два вложени цикъла и допълнителен масив 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]. Така намирайки и отпечатвайки предходния елемент докато има такъв, можем да намерим елементите съставящи най-дългата нарастваща подредица в обратен ред (от последния към първия).