Obliczanie zysku

chce rozwiazac takie zadanie

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

ale nie widze analogii nawet, np w pierwszym, mamy dodatnie: 1,4,5 i ujemne: -2,-2 ; jak z tego wyszlo 9 ? nie rozumiem tresci zadania tez, ominal pierwszy koncert czyli 1 i ostatni -2 tak ? to i tak nie wychodzi 9, nawet jak ominal ostatni -2 to nie wychodzi 9, a w tresci jest ze moze ominac pierwszy lub drugi albo dwa naraz chyba. O co chodzi wyjasni ktos ?

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.

Przykład
Wejście

5
1
-2
4
5
-2

Wyjście

9

5 miast
1 odpada, 2 odpada
3 i 4 zostaje więc (4 + 5)
5 odpada
wyjście 9

Pominął pierwsze dwa miasta, rozpoczął w trzecim i zakończył w czwartym (pomijając ostatni): 4 + 5 = 9.
W drugim przypadku w ogóle nie opłaca mu się jechać (technicznie "rozpoczął" po ostatnim mieście), więc zysk wynosi 0.

Najprostsze rozwiązanie mogłoby być następujące:
-Dodawaj wszystkie liczby
-Zapamiętaj sumę
-Kolejno usuwaj pierwsze/ostatnie liczby
-Porównuj sumę (łączny zysk)
-Wyświetl zysk który okazał się największy
Zyski dla danej kombinacji możesz zapamiętywać na przykład w tabeli o rozmiarze będącym liczbą kombinacji możliwych do uzyskania przy skreślaniu kolejnych zysków lub strat (dla przykładu pięciu miast będzie to rozmiar: 5 + 4 + 3 + 2 + 1 + 1(bo jeszcze możliwość, że nic nie skreślisz) = 16).
Wiem, że to rozwiązanie dość "pamięciochłonne", ale póki co tylko takie przychodzi mi do głowy.

Powodzenia ;)

Jest lepszy sposób, bez tablicy. Sumujesz wszystkie liczby i jeśli:

• suma jest większa od aktualnego maksimum to za maksimum podstawiasz sumę
• suma jest mniejsza od zera - na pewno zacznie później/już zrezygnuje, wiec suma = 0
  Swoją drogą zamiast kopiować zadanie trzeba było dać linka do SPOJa, bo stamtąd pochodzi.

Eeee, na to już jest metoda - algorytm Kadane'a: https://en.wikipedia.org/wiki/Maximum_subarray_problem (Tablica jest niepotrzebna, O(n))

Wydaje mi się, że autor chciał żeby mu rozjaśnić treść, a nie serwować gotowe rozwiązanie na tacy...