Здравейте,

От няколко часа се опитвам да реша задачата, но винаги има изключение, което не съм хванал.

Може ли някой, който успешно я е решил, да ми подскаже, тъй като обяснението не успявам да разбера, а и в самия отговор(примерният) на задачата има несъответствие(според мен).

Та задачата е:

Write a program, which finds the maximal sequence of increasing elements in an array arr[n]. It is not necessary the elements to be consecutively placed. E.g.: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} -> {2, 4, 6, 8}. ( тук, най-верният отговор(от трите възможни) мисля, че трябва да е {2, 4, 5, 8}, а не този, който е даден за пример {2, 4, 6, 8}.

Упътването е:

 Задачата може да се реши с два вложени цикъла и допълнителен масив 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]. Така намирайки и отпечатвайки предходния елемент докато има такъв, можем да намерим елементите съставящи най-дългата нарастваща подредица в обратен ред (от последния към първия).

Та може ли някой, да ми помогне и да каже, кой е найстина правилниятт алгоритъм. Аз се опитвам да я реша спрямо този масив: int[] digitsArray = { 3, 7, 4, 4, 6, 8, 6, 9, 3, 4, 6, 9, 2, 3, 6, 1, 5, 6, 9, 1 } -> където има два верни отговора {3,4,6,8,9} и {2,3,5,6,9} и "по-верният" трябва да е вторият.