Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } PSOMS 1 (psoms-1) Memory limit: 3 MB Time limit: 1.00 s Zadanie polega na znalezieniu podciągu spójnego o maksymalnej sumie (PSOMS). Dla przypomnienia: podciąg spójny ciągu jest to dowolny jego spójny kawałek od pewnego elementu do pewnego innego (w szczególności pusty ciąg jest podciągiem spójnym dowolnego ciągu). Pojęć sumy i maksimum chyba nie trzeba tłumaczyć. Napisz program, który: wczyta ciąg liczb, wyznaczy wartość podciągu spójnego o maksymalnej sumie i wypisze wynik na standardowe wyjście. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb całkowitych Ti, pooddzielanych pojedynczymi odstępami. Są to kolejne wyrazy ciągu, dla którego należy wyznaczyć wartość PSOMSa. Wyjście W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – wartość maksymalnego podciągu o maksymalnej sumie. Ograniczenia 1 ≤ N ≤ 1 000 000,  − 109 ≤ Ti ≤ 109. Częściowa punktacja W testach wartych łącznie 40% maksymalnej punktacji: N ≤ 5 000. Przykład Input Output 8 2 -5 3 4 -2 5 -7 1 10

Input	Output
`8 2 -5 3 4 -2 5 -7 1`	`10`