Wątek przeniesiony 2015-03-28 14:57 z C/C++ przez Shalom.

Znajdowanie najdłuższego ciągu(rosnącego bądź malejącego)

0

Dzień dobry, jestem początkujący jeśli chodzi o programowanie w C++, ale mam pewne zadanie z którym nie mogę się uporać

ZADANIE

Rozważmy losowy ciąg liczb naturalnych C. Podaj długość oraz sumę elementów najdłuższego możliwego monotonicznego i spójnego zarazem podciągu ciągu C. W przypadku niejednoznaczności odpowiedzi wskaż pierwszy taki ciąg począwszy od lewej strony.

WEJŚCIE

Wiersz opisujący elementy ciągu C oddzielone znakiem odstępu (kod ASCII 32) zakończony znakiem końca pliku (EOF).

WYJŚCIE

Wiersz zawierający dwie liczby będące rozwiązaniem postawionego problemu oddzielone znakiem odstępu.

OGRANICZENIA

Długość ciągu C dodatnia i ograniczona przez 107, elementy rozważanego ciągu zawarte w przedziale wartości [0,109].

LIMITY

Oczekiwana złożoność czasowa rzędu O(n). Oczekiwana złożoność pamięciowa rzędu O(1).

PRZYKŁAD 1

wejście:

8 4 2 3 2

wyjście:

3 14

Oto co dałem radę napisać

#include <iostream>
#include <cstdio>
//#include <conio.h>

using namespace std;

int main(){
    int obecnaL=0;
    int poprzedniaL=0;
    long long int sumaO=0;
    int dlugoscO=0;
    long long int sumaM=0;
    int dlugoscM=0;
    int powtorzenia=1;
    int stan= 0;

    scanf("%d", &poprzedniaL);
    sumaO+=poprzedniaL;
    dlugoscO++;

    while(scanf("%d", &obecnaL ) != EOF){
    if(stan==0){
        if(obecnaL>poprzedniaL){
            stan=1;
        }else{
            stan= -1;
        }
    }
    if(stan==1){
        if(obecnaL>=poprzedniaL){
            sumaO+=obecnaL;
            dlugoscO++;
            if(obecnaL==poprzedniaL) powtorzenia++; else powtorzenia =1;
        }else{
            sumaM=sumaO;
            dlugoscM=dlugoscO;
            sumaO=poprzedniaL*powtorzenia;
            dlugoscO=powtorzenia;
            powtorzenia=1;
            stan=0;
        }
    }else if(stan==-1){
        if(obecnaL<=poprzedniaL){
             sumaO+=obecnaL;
            dlugoscO++;
            if(obecnaL==poprzedniaL) powtorzenia++; else powtorzenia =1;
        }else{
            sumaM=sumaO;
            dlugoscM=dlugoscO;
            sumaO=poprzedniaL*powtorzenia;
            dlugoscO=powtorzenia;
            powtorzenia=1;
            stan=0;
        }
    }

    poprzedniaL = obecnaL;
    }
    cout<< dlugoscM << " " << sumaM;
    return 0;
}

Co najdziwniejsze, przykład podany w treści jest wykonywany bezbłędnie przez ten program, ale każdy inny przykład zwraca mi odpowiedź "0 0". Nie jestem w stanie znaleźć w czym leży problem, program wydaje mi się być napisany poprawnie, mam nadzieję, że ktoś bardziej doświadczony jest w stanie powiedzieć gdzie leży błąd
EDIT: Zapomniałem dodać, ciąg może być "rosnący lub stały" albo "malejący lub stały"

0

Google: Najdluzszy podciag rosnacy

Masz tam kod w c++. Nie sprawdzałem, czy działa, ale coś takiego ciężko zepsuć.

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