28ος ΠΔΠ Καμπ (juniors)
Μετοχές (metoxes2)

Ο Μίλτος βρίσκεται στην ευχάριστη θέση να διαθέτει αξιόπιστες πληροφορίες για την τιμή μιας μετοχής στο χρηματιστήριο και θέλει να τις εκμεταλλευτεί! Συγκεκριμένα γνωρίζει τη μεταβολή της τιμής μιας μετοχής για κάθε μία από τις επόμενες \(N\) ημέρες. Αν, για παράδειγμα, η μεταβολή για κάποια ημέρα είναι \(-3\) (αντίστοιχα, \(4\)), αυτό σημαίνει ότι η τιμή της μετοχής μειώθηκε κατά \(3\) ευρώ (αντίστοιχα, αυξήθηκε κατά \(4\) ευρώ) σε σχέση με την τιμή της προηγούμενης ημέρας.

Ο Μίλτος μπορεί να επιλέξει την ημέρα που θα αγοράσει την μετοχή, αλλά θα πρέπει υποχρεωτικά να την πουλήσει μετά το τέλος της \(N\)-οστής ημέρας. Επιπλέον, ο Μίλτος δεν είναι καθόλου ριψοκίνδυνος και θέλει από τη στιγμή που θα αγοράσει την μετοχή, η τιμή της να παραμένει μεγαλύτερη από την τιμή στην οποία την αγόρασε.

Να γράψετε ένα πρόγραμμα που θα βοηθήσει τον Μίλτο να υπολογίσει το μέγιστο κέρδος που μπορεί να πετύχει αν αγοράσει την μετοχή την καλύτερη δυνατή στιγμή.

Αρχεία Εισόδου (metoxes2.in):

Η πρώτη γραμμή της εισόδου θα περιέχει το πλήθος \(N\) των ημερών. Η δεύτερη γραμμή της εισόδου θα περιέχει \(N\) ακέραιους αριθμούς \(a_i\) που αντιστοιχούν στη μεταβολή της τιμής της μετοχής την \(i\)-οστή ημέρα.

Οι αριθμοί θα χωρίζονται μεταξύ τους με κενά διαστήματα.

Αρχεία Εξόδου (metoxes2.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό: το μέγιστο κέρδος που μπορεί να επιτύχει ο Μίλτος.

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

metoxes2.in	metoxes2.out
8 -1 3 -4 5 -1 4 0 -2	6

Εξήγηση 1^ου παραδείγματος: Ο Μίλτος μπορεί να αγοράσει την μετοχή την 3η ημέρα (στο τέλος της). Έστω ότι η τιμή της μετοχής εκείνη τη στιγμή είναι \(x\). Τότε την 4η ημέρα θα είναι \(x + 5\), την 5η θα είναι \(x + 5 - 1 = x + 4\), κ.ο.κ. Την τελευταία ημέρα, η τιμή της μετοχής θα είναι \(x + 5 - 1 + 4 + 0 - 2 = x + 6\), κι έτσι αν την πουλήσει τότε θα έχει κέρδος \((x + 6) - x = 6\). Επιπλέον, από την 4η ημέρα και μετά, η τιμή της μετοχής είναι πάντα μεγαλύτερη από \(x\). Αν ο Μίλτος επέλεγε να αγοράσει την μετοχή κάποια άλλη μέρα δεν θα κατάφερνε να έχει κέρδος μεγαλύτερο του \(6\).

2^o

metoxes2.in	metoxes2.out
10 5 -6 7 -8 14 12 -11 9 -5 4	23

Εξήγηση 2^ου παραδείγματος: Ο Μίλτος μπορεί να αγοράσει την 4η ημέρα (έστω σε τιμή \(x\)). Τις επόμενες ημέρες, η τιμή της μετοχής θα είναι αντίστοιχα: \(x + 14\), \(x + 26\), \(x + 15\), \(x + 24\), \(x + 19\), \(x + 23\), που είναι πάντα τουλάχιστον \(x\). Έτσι ο Μίλτος επιτυγχάνει το μέγιστο κέρδος \(23\) όταν την πουλήσει την τελευταία μέρα.

3^o

metoxes2.in	metoxes2.out
5 1 2 1 2 -10	0

Εξήγηση 3^ου παραδείγματος: Όποια μέρα και αν αγοράσει ο Μίλτος, την τελευταία ημέρα η μετοχή θα έχει μεγάλη πτώση και σίγουρα θα βγει χαμένος. Τον συμφέρει λοιπόν να μην αγοράσει καθόλου και να έχει κέρδος \(0\).

Περιορισμοί

• \(2 \leq N \leq 1.000.000\).
• \(1.000 \leq a_i \leq 1.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(16\) MB.