Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FZI_STEF - Stefan

Pan Stefan, powszechnie znany piosenkarz, planuje swoją największą trasę koncertową. Starannie wybrał miasta, w których chciałby zagrać oraz ustalił kolejnośc ich odwiedzania. Niestety badania rynku wykazały, że nie we wszystkich miastach zarobi (być może koszty organizacji koncertu będą większe niż zyski z biletów). Pan Stefan wydrukował już plakaty z listą planowanych koncertów, więc jedyne zmiany, na jakie mógłby sie zgodzić, to rozpoczęcie trasy być może później niż w pierwszym mieście na liście oraz zakończenie być może wcześniej niż w ostatnim mieście na liście.

Zadanie

Wyznacz, jaki jest największy możliwy zysk Pana Stefana na trasie otrzymanej w opisany powyżej sposób.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę naturalną n (1≤n≤100 000) oznaczającą liczbę miast na trasie. W każdej z kolejnych n linii znajduje się jedna liczba całkowita z przedziału [-100 000,100 000] oznaczająca całkowity zysk lub stratę z organizacji koncertu w danym mieście.

Wyjście

Należy wypisać maksymalny możliwy zysk Pana Stefana.

Przykład

Wejście

5
1 
-2
4
5
-2

Wyjście

9

Wejście

2
-1
-2

Wyjście

0

Dodane przez:Rafal Nowak
Data dodania:2007-02-08
Limit czasu wykonania programu:0.117s-0.200s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ADA95 ASM32 BASH BF CSHARP C99 CLPS LISP clisp LISP sbcl D ERL FORTRAN GOSU HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OBJC OCAML PAS-GPC PERL PERL6 PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST SQLITE VB.NET WHITESPACE
Pochodzenie:Fajne Zawody Informatyczne

ukryj komentarze
2017-07-02 20:18:58
in:
11
14 -8 6 -2 4 -6 5 -5 7 -4 10
out:
21
2017-05-20 12:49:45
Nie da się dodać programu w Javie..
2017-05-18 23:20:30 Wojciech Bomba
Czemu nie można przesłać rozwiązania w Javie - są jakieś metody (o których mi nie wiadomo) które rozwiązują ten problem?
2017-04-24 23:52:11 Konrad
W pierwszym chodzi o to że 9 jest sumą 4 i 5, pan stefan wcale nie musi zaczynać od początku trasy(1, -2) i może ją skończyć, kiedy będzie potencjalnie największy zysk z koncertów. Ewentualnie może w ogóle nie jechać by nie przysporzyć sobie długów :P
2017-02-11 21:28:49
Przez ponad pięć godzin kombinowałem, dlaczego otrzymuję "błędna odpowiedź". Okazało się, że zapomniałem o enterze (endl) po zysku, także chciałbym na to zwrócić uwagę.
2017-01-29 14:42:00
Przeczytaj "Wejście", pierwsza liczba oznacza liczbę miast a nie zysk
2017-01-27 17:11:34
Nie do końca to rozumiem :
5
1
-2
4
5
-2 (To miasto mozna z trasy usunac bo jest na koncu list)
Tak wiec zysk z tego powyzej powinien byc : 5+1-2+4+5 = 13 nie 9
albo tu :
2
-1
-2
Skoro może skończyć skończyć wcześniej niż w ostatnim mieście to zysk powinien się równać 2(Drugie i trzecie miasto usuwamy z trasy)
2013-12-23 21:41:34 Micha³ Czerwionka
Kilka testów, które sam wymyśliłem i pozwoliły mi dojść do rozwiązania:
in: 1000 -800 999 -800
out: 1199
in: 105 -150 108 -50
out: 108
in: 101 5 -150 5 100 -50 3
out: 106
in: 2 -1 2 -1 2 -1 2
out: 5
in: 100 5 -150 5 100 3 -4
out: 108
in: 100 -3000 -5000 -3000 -9000 100 -200 -10000
out: 100
in: 100 5 -105 4 100 -1 -1 -1 -112 130
out: 130

Ostatnio edytowany: 2015-01-14 04:27:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.