Największa suma - pseudokod

Mam o to taki pseudokod, który liczy największą sumę spójnych elementów w danym ciągu:)

 MAKSYMALNA SUMA (A,n)
suma -> 0
dotądNaj -> 0
	for i <- 1 to n
		if (suma > -A[i]) then
			suma <- suma + A[i]
		else
			suma <- 0
		endif
		dotądNaj <- MAX (dotądNaj, suma)
return dotądNaj 

W tym algorytmie jest jedna pętla o stałej długości = n, brak pętli zagnieżdżonych, czyli wnętrze pętli jest O(1), a n*O(1) = O(n) - złożoność obliczeniowa tego algorytmu. Teraz rodzi się pytanie jak to ładnie zapisać matematycznie? Dać dowód na to, że jest taka złożoność:)

Ktoś pomoże?

Skoro pętla wykona się n + 1 razy, to ilość wykonań tej pętli to n + 1.

Jako, że n + 1 < 2n dla n > 1, to złożoność asymptotyczna tej pętli to O(n), a nawet theta(n), bo pętla wykona się tyle samo razy w każdym przypadku.

W pętli jest jakaś stała liczba operacji, oznaczmy ją C, jako że n + 1 + C < 2n dla n > d, gdzie d oznacza liczbę dla których funkcja 2n jest większa od n + 1 + C, gdzie C jest stałą, więc n + 1 + C = O(n).

Poza tematem pisz ładniejsze pseudokody. Zastrzeżenia:

1. W warunku piszesz <-, zamiast <=, jak się przyjęło w większości języków programowania i pseudokodów. Dodatkowo tak samo zapisujesz przypisanie, przez co te dwie operacje mylą się gdy się czyta kod. Do tego warunek (suma > -A[i]), a jakbyś miał zapisać >=, to co? Wtedy wyglądało by to tak (suma >- -A[i]). Bardzo brzydko - łatwo można się pomylić.

2. Po suma := 0 piszesz end, a gdzie był begin, czy inny nawias rozpoczynający?

3. Co znaczy endif?

Zanim wstawisz następnym razem kod na forum, zadbaj wcześniej o czytelność.

mam w ramach zajec przerobic pewien algorytm w pseudokodzie i w takim samym pseudokodzie zapisac.
Endif - oznacza koniec operacji warunkowej:)

 MAKSYMALNA SUMA (A,n) 
 dotądNaj <- 0 
 for d <- 1 to n 
    do suma <- 0 
       for g <- d to n 
          do suma <- suma + A[g] 
             dotąd naj <- MAX (dotądNaj, suma) 
 return dotądNaj

do suma < -suma+A[g] to pętla? :)

MaksymalnaSuma (A, n)
 	dotądNaj := 0
 	for d:= 1 .. n
 		suma:= 0
 		for g:= d .. n
 			suma:= suma + A[g]
 			dotądNaj:= MAX( dotądNaj, suma )
 	return dotądNaj
 	
 	
MAKSYMALNA_SUMA (A,n)
	suma := 0
	dotądNaj := 0
        for i := 1 .. n
                //if suma > -A[i]
                //        suma := suma + A[i]
                //else
                //        suma := 0
                suma:= MAX( suma + A[i], 0 );

                dotądNaj := MAX ( dotądNaj, suma )
	return dotądNaj

a czemu pętla się wykona n+1 a nie n razy?

Pętla się wykona n + 1 razy, ponieważ przy n + pierwszym sprawdzeniu warunku pętla przyjmuje wartość logiczną false.

Pętla for i := 1 to n zawsze wykonuje się n + 1 razy, ponieważ to nie jest tak, że jakoś jest odmierzana wartość i do końca (tak błędnie mogą sobie niektórzy wyobrażać), tylko za każdym razem jest sprawdzany warunek.

Dla n = 2 pętla przyjmie wartość true dla i = 1 i i = 2. Następnie warunek sprawdzany jest jeszcze raz, dla i = 3 i wtedy mamy już wartość false. Mamy 2 + 1 razy, czyli n + 1 razy.