Zablokowane Potrzebna pomoc....

[TeoTN]

Jak zrobić takie zadanie??? Poproszę, w miarę możliwości, o opisany kod (C++).

 

 

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

[SLy]

Nie znam C++, więc nie napiszę kodu, ale do głowy przychodzi mi takie rozwiązanie:

1. Pobierasz od użytkownika liczbę miast - n.

2. Tworzysz tablicę n-elementową i dla każdego jej elementu generujesz losową liczbę z zakresu [-100 000; 100 000].

3. "Przelatujesz" n razy całą tablicę sumując elementy od 1 do n, 1 do n-1 ... 1 do 2, potem 2 do n, 2 do n-1 itd. aż do n-1 do n.

4. Wyniki możesz zapisywać do innej tablicy i potem wybrać największy, albo wprowadzić do pętli jakąś zmienną np. max.

[kryniak]

Myślenie algorytmiczne się kłania ;]

Zobacz, czy tak:

#include <iostream>
using namespace std;
int main()
{
   int n,sum=0,max=0,liczba;
   cin >> n;
   while (n--)
   {
       cin >> liczba;
       sum = liczba>0 ? sum+liczba : 0;
       max = max<sum ? sum : max;
   }
  cout << max;
}

Pisałem w ciemno, więc mogą być błędy.

[TeoTN]

dzięki bardzo - jeszcze tylko małe pytanko: co oznacza "?" w

max = max<sum ? sum : max;

:confused:

[kryniak]

To jest tzw. operator trójskładniowy, czyli

max = max<sum ? sum : max;

zastępuje

if (max<sum)

max=sum;

else

max=max;

 

Możesz oczywiście pozmieniać to, ale ja lubię mniejszy bajzel w kodzie. A właśnie, kod w ogóle działa?

:)

[TeoTN]

ok, dzięki bardzo :D

 

EDIT: Działa, nie rozpatrywał tylko jednej możliwości, ale poprawiłem :D