Algorytm na maksymalną sumę elementów spójnych tablicy

Chiałbym prosić o pomoc w znalezieniu algorytmu na maksymalna sumę elementów spójnych tablicy. Nie chcę gotowego kodu (choć się nie obrażę :P) ale ogólnego schematu działania algorytmu.

Elementy spójne tablicy to takie elementy którego poprzedni ma indeks o 1 mniejszy od obecnego. Dla przykładu elementy o indeksach 2,3,4 są spójne. Podobnie od 3 do 10. Lecz elementy o indeksach 3,4,6,7 nie są już spójne ponieważ brakuje 5. Mam nadzieję, że większośc rozumie co mam na myśli.

Potrzebuję algorytm który z jednowymiarowej tablicy integerów (dodanie jak i ujemne wartości) wyszuka taką sumę, która będzie największą sumą wszystkich możliwych kombinacji elementów spójnych. Dla przykładu:

Tablica = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]

Łopatologicznie mozna to ująć tak, szukamy sumy z elementów:
Suma := Tablica[0]
Suma := Tablica[0] + Tablica[1]
Suma := Tablica[0] + Tablica[1] + ... Tablica[9]
Suma := Tablica[1] + Tablica[2]
...
Suma := Tablica[8] + Tablica[9];
Suma := Tablica[9];

Z powyższych sum trzeba wyznaczyć największą. Dla podanego przykładu suma taka wynosi 187 - jest to suma elementów o indeksach od 1 do 5.

Jest tylko jeden haczyk. Algorytm musi mieć złożoność rzędu n, czyli musi zwierać się w pętli od 0 do n. Wszelkie rozwiązania z pętlami podwójnymi [O(n^{2)] lub nawet potrójnymi odpadają [O(n}3)].

Kod moze i w C++ ale bajecznie prosty:

#include <iostream>

using namespace std;

int main()
{
  int tablica [] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
  int suma = - 12345;
  int aktualna = 0;
  for (int j = 0; j < 10; j++)
  {
    aktualna += tablica[j];
    if (aktualna > suma)
     suma = aktualna;
    if (aktualna < 0)
     aktualna = 0;
  }
  cout << suma << endl;
  cin.get();
}

Dodam jeszcze, ze algorytm wymyslilem kiedys do jakiegos zadania, i moze nie dzialac calkiem poprawnie bo zadanie bylo troche inne, a nie mam czasu poprawic, ale wydaje mi sie, ze zasada powinna byc ta sama.

// hmm - może sam skasuj tego posta zanim ktoś zobaczy ;) - deti
// a to niby dlaczego? - autor
// hmm - czasem mam takie akcje po 8miu godzinach programowania, mea culpa :| - deti

co do

Algorytm jest ok. Dzięki [browar] || [soczek]
to ja wole [browar] chociaz dzisiaj to by [soczek] sie przydaj ;)

Algorytm jest ok. Dzięki [browar] || [soczek]