Sesja

W ciągu elementów tablicy liczb całkowitych wyznaczyć podciąg spójny złożony z elementów tej tablicy kolejno następujących po sobie o największej sumie. W przypadku, gdy ta suma jest ujemna przyjmujemy, że jest równa 0. Wyznaczyć numer początku i końca wycinka tablicy o maksymalnej sumie.(tablicę numerujemy od 0).

Wejście:

W pierwszym wierszu podajemy liczbę całkowitą n<10^6 będącą liczbą powtórzeń serii danych. W kolejnych wierszach podajemy k<1000 liczb całkowitych większych od -10^9 i i mniejszych od 10^9, rozdzielonych spacją i zakończonych znakiem nowej linii.

Wyjście:

Na wyjściu w każdym przypadku testowym dostajemy trzy liczby całkowite nieujemne rozdzielone spacją będące odpowiednio: maksymalną niujemną sumą spójnego podciągu, początkiem podciągu i końcem podciągu.

Przykład
Wejście:
3
1 2 3
5 6 -20 11 5 6
2 77 5 -5 -6 -11 11
Wyjście:
6 0 2
22 3 5
84 0 2

Wskazówka:
Najlepszy algorytm jest o złożoności liniowej. 
Weź kartkę i długopis i zacznij sumować.
Co najlepiej zrobić, gdy suma zaczyna być ujemna?