Najdłuższy podciąg rosnący tablicy

0

Witam, mam problem z kodem do znalezienie (wypisania) najdluższego podciągu tablicy.

void podciag(int tablica[])
{
    int max=0;
    int temp=1;
    for ( int i=1; i<=10; i++)
    {
        if (tablica[i-1]<tablica[i])    
        temp++;
        else temp=1;
        if (max<temp) max=temp;
    }
    cout<<"Najwiekszy rosnacy sklada sie z: "<<max<<" liczb.";
}

Tym kodem znajduję długość najdłuższego podciągu rosnącego, ale w jaki sposób mam zapamiętać miejsce w którym ten podciąg się zaczyna (lub kończy), nie wiem w którym miejscu mam wpisać formułę do zapamiętania indeksu. Z góry dziękuje za pomoc.

0

wiesz ze do tej funkcji mozesz jedynie 11 elementowa tablice przeslac?

if (tablica[i-1]<tablica[i])   
{ 
  temp++;
  indeks = i-1;
}
else 
  temp=1;

o coś takiego chodzi?

0

Ja tylko dodam że wcale nie szukasz najdłuższego podciągu tylko najdłuższy podnapis (substring, tak to się bodaj tłumaczy - w każdym razie, podnapis jest spójny a podciąg niekoniecznie).
(Np. najdłuższy podciąg rosnący [1, 4, 5, 3, 2, 7, 4, 8] to [1, 3, 4, 8], a podnapis to [1, 4, 5])

W zależności od twoich wymagań może to być albo nie być to czego chcesz. Jeśli dostałeś na zadanie domowe najdłuższy podciąg rosnący to najprawdopodobniej nie jest.

0

W takim przypadku nie będzie to działało bo zawsze będzie zwracało taką samą wartość. A chce mieć dostęp do tych indeksów żeby później móc wyświetlić te ciągi, ale nie wiem jak sobie z tym poradzić i co jeżeli będą dwa ciągi o takiej samej długości (np o 3 znakach).

Ps. tak wiem, że to jest tylko dla 10 elementowej tablicy.

0

Tak chodzi mi o podłańcuch / substring czyli dla 1 23 4 58 93 30 1 20 30 1 wynik powinien być 4 58 93 oraz 1 20 30.

1

Dałoby się to zapisać zwięźlej, ale chyba ujdzie:

void longest_substring(int arr[]) {
    int curr_len = 0, max_len = 0, start = 0;
    for (int i = 1; i <= 10; i++) {
        if (arr[i-1] < arr[i]) {
            curr_len++;
            if (curr_len >= max_len) { // > - pierwszy, >= - ostatni
                max_len = curr_len;
                start = i - curr_len + 1;
            }
        } else {
            curr_len = 1;
        }
    }

    for (int i = 0; i < max_len; i++) {
        std::cout << arr[start + i] << " ";
    }
}

co jeżeli będą dwa ciągi o takiej samej długości (np o 3 znakach).

To już zależy od tego co chcesz z nimi robić ;].
W komentarzu co robić jeśli chcesz pierwszy albo ostatni. Innych sensownych opcji nie ma, ewentualnie możesz zwracać błąd.
Z tego co pamiętam, najdłuższy definiuje się zazwyczaj jako taki że nie ma dłuższych, więc wystarczy wybrać dowolny.

0

Dzięki za pomoc, widzę że działa ten algorytm, ale jest pewien problem którego jeszcze nie rozgryzłem w Twoim rozwiązaniu. W pewnych sytuacjach podaje ciąg np 4 elementowy którego 3 elementy to ostatnie elementy tablicy a czwarty element już wychodzi poza jej zakres i jest zupełnie inną wartością

0

Ok, już znalazłem błąd - banalny, pętla for miała za daleki zakres w moim przypadku :) Dzięki bardzo za wszelką pomoc (i to o tej godzinie!), przywracacie wiarę w ludzi.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0