Najdłuższy spójny ciąg monotoniczny.

0

Witam.
Próbuję napisać program mający na celu wyszukanie najdłuższego SPÓJNEGO podciągu monotonicznego w ciągu znaków i wyznaczenie jego liczebności (ilości elementów) oraz sumy tych elementów. Nieco ułomnie ale prawie "udało mi" się go napisać. Dla większej części danych testowych program działa poprawnie a dla niektórych się psuje... Niestety nie jestem w stanie spostrzec prawie żadnych zależności ( w jednym przypadku gdy mam kilka losowych liczb i b. dużo jedynek => szukanym ciągiem jest ciąg jedynek suma jest za duża o 1 i liczebność też) ponieważ pliki z liczbami zawierają przykładowo po 40000 liczb. :( Czy mógłby ktoś powiedzieć czym może to być spowodowane?? Poniżej załączam kod - JESTEM DOSKONALE ŚWIADOMY, ŻE PEWNIE MOŻNA TO NAPISAĆ LEPIEJ JEDNAK NA RAZIE CHCĘ SIĘ SKUPIĆ JEDYNIE NA ROZWIĄZANIU PROBLEMU - jeżeli ktoś pisał coś podobnego lub chce przedstawić swoją własną ideę to proszę bardzo - może pomoże mi to w rozwiązaniu mojego problemu. Mam nadzieję, że komuś uda odczytać się w tym chaosie... dodałem trochę komentarzy celem próby ułatwienia sprawy...

#include <iostream>
#include <cmath> //pow();
#include <vector>
#include <fstream>
using namespace std;

int main()
{
    /* wczytanie danych z pliku do wektora - prawdopodobnie część ta jest ok*/
    fstream plik;
    vector<long>dane;
    long x;
    plik.open("dane.txt",ios::in);
    if(plik.good()==false){
        cout<<"Cos poszlo nie tak"<<endl;
    }
    while((!plik.eof())&&(dane.size()<10000000)){
    	plik>>x;//warunki wynikają z kryteriów zadania, jakie zostało mi postawione
    	
    	if(x>=0&&x<=1000000000)dane.push_back(x);
    }
    
    plik.close();
    ;
    long i;
    long ilosc=dane.size();
	long pom1=1,longg=1,pom2=1,indeks_mal=0,indeks_ros=0,longg1=1,longg2=1;

    /*wyznaczenie dlugosci i indeksu na kotorym konczy sie  najdluzszy niemalejacego spojny ciag*/
    for(i=0;i<(ilosc-1);i++){
        if(dane[i]<=dane[i+1]){
            pom1++;
            if(pom1>=longg1){
            longg1=pom1;
			indeks_ros=i;            
            }
        }
        else{
        pom1=1;//bylo 1
        }
        /***********************************/
    
        /*wyznaczenie dlugosci i indeksu na kotorym konczy sie  najdluzszego nierosancy spojny ciag*/
        if(dane[i]>=dane[i+1]){
            pom2++;
            if(pom2>=longg2){
			longg2=pom2; 
			indeks_mal=i;
		}
        }
        else{
		 pom2=1;//bylo 1
    }
    }
    

/*wybranie odpowiedniego ciagu... jezeli mamy 2 ciagi tej samej dlugosci to wybieramy ciag najbardziej po lewo*/
    long index,suma_calk=0,warunek;
	if(longg1>longg2){
		cout<<"If pierwszy"<<endl;
		longg=longg1;
		index=indeks_ros-(longg-2);
		warunek=index+longg;
		for(i=index;i<warunek;i++){
		suma_calk+=dane[i];
	}
	}
	else if(longg1<longg2){
		cout<<"PETLA DLA CIAGU MELEJACEGO"<<endl;
		cout<<"indeks malejacy:"<<indeks_mal<<endl;
		longg=longg2;
		index=indeks_mal-(longg-2);
		warunek=index+longg;
		for(i=index;i<warunek;i++){
		suma_calk+=dane[i];
	}
	}
	else{
	//wybieram ciag po lewej
	longg=longg1;
		if(indeks_mal<indeks_ros){
			index=indeks_mal-(longg-2);
			warunek=index+longg;
			for(i=index;i<warunek;i++){
			suma_calk+=dane[i];
		}
		}
		else{
			index=indeks_ros-(longg-2);
			warunek=index+longg;
			for(i=index;i<warunek;i++){
			suma_calk+=dane[i];
		}
	}
}
	cout<<"Suma to: "<<suma_calk<<" Liczebnosc: "<<longg<<endl;




    return 0;
}

Dzięki...

0

Sprawdź działanie swojego algorytmu na ciągu 1,1,1.

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