#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void znajdz_najwiekszy_podciag_niemalejacy(int ciag[], int liczba_wyrazow, int &poczatek_najw_ciagu, int &koniec_najw_ciagu, int &najwieksza_suma)
{
	poczatek_najw_ciagu = koniec_najw_ciagu = 0;
	najwieksza_suma = ciag[poczatek_najw_ciagu];
	int poczatek_sprawdz_ciagu = poczatek_najw_ciagu, suma_sprawdz_ciagu = najwieksza_suma;
	for(int koniec_sprawdz_ciagu = 1; koniec_sprawdz_ciagu < liczba_wyrazow; koniec_sprawdz_ciagu++)
		if(ciag[koniec_sprawdz_ciagu]>=ciag[koniec_sprawdz_ciagu-1])			// Mamy ciag niemalejacy
		{
			suma_sprawdz_ciagu += ciag[koniec_sprawdz_ciagu];
			if(suma_sprawdz_ciagu > najwieksza_suma)									// Znaleziono nowy najwiekszy
			{
				koniec_najw_ciagu = koniec_sprawdz_ciagu;
				poczatek_najw_ciagu = poczatek_sprawdz_ciagu;
				najwieksza_suma = suma_sprawdz_ciagu;
			}
		}
		else												        // Koniec ciagu niemalejacego, zaczynamy nowy ciag
		{
			poczatek_sprawdz_ciagu = koniec_sprawdz_ciagu;
			suma_sprawdz_ciagu = ciag[koniec_sprawdz_ciagu];
		}
}

void Testuj()
{
	const int LICZBA_WYRAZOW = 10;
	int ciag[LICZBA_WYRAZOW];

	// Przygotowanie losowego ciagu i wypisanie go na ekranie
	for(int i=0; i<LICZBA_WYRAZOW; i++)
	{
		ciag[i] = rand() % 10;
		if(i>0)
			cout << " ";
		cout << ciag[i];
	}
	cout << endl;

	int poczatek, koniec, suma;
	znajdz_najwiekszy_podciag_niemalejacy(ciag, LICZBA_WYRAZOW, poczatek, koniec, suma);
	cout << "Poczatek: ciag[" << poczatek << "]=" << ciag[poczatek] <<
			", koniec: ciag[" << koniec << "]=" << ciag[koniec] <<
			", suma ciagu: " << suma << endl;
}

int main()
{
    srand(time(NULL));
    for(int i=0; i<10; i++)
		Testuj();
}