Algorytmy 1
Problem maksymalnej podtablicy
Mając tablicę $n$ liczb całkowitych, twoim zadaniem jest znalezienie maksymalnej sumy wartości w ciągłej, niepustej podtablicy. Dokładniej, dany jest ciąg $a_1, a_2, \ldots, a_n$. Znajdź $$\max_{1\leq i\leq j\leq n} (a_i+a_{i+1}+\ldots+a_j).$$
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.
Wyjście
Pierwszy i jedyny wiersz wyjścia zawiara szukaną wartość.
Ograniczenia
- $1 \le n \le 2\cdot 10^5$
- $-10^9 \le a_i \le 10^9$
Przykłady
Wejście 1
8
-1 3 -2 5 3 -5 2 2
Wyjście 1
9
Wejście 2
6
-1 -1 -1 -3 -3 -3
Wyjście 2
-1