Μέγιστο Άθροισμα Υποπίνακα

Δίνεται θετικός ακέραιος ~N~ και ακολουθία ~N~ ακέραιων αριθμών ~\alpha_1, \alpha_2, ... \alpha_N~. Ζητάται να βρεθεί το μέγιστο άθροισμα διαδοχικών στοιχείων της ακολουθίας :

$$\displaystyle \max{S_{ij}},\qquad S_{ij} = \sum_{k=i}^{j} \alpha_k $$

Μορφή εισόδου

Στην πρώτη γραμμή δίνεται ένας θετικός αριθμός ~T~. Μετά, ~T~ ερωτήματα ακολουθούν:

Για κάθε ερώτημα δίνεται θετικός ακέραιος ~N~, μόνος του σε μία γραμμή, και στην επόμενη ~N~ αριθμοί, χωρισμένοι με κενό, τα ~\alpha_i~.

Μορφή εξόδου

Να εκτυπώσετε ~T~ γραμμές, όπου στην ~i~-οστή γραμμή υπάρχει μοναδικός αριθμός: το μέγιστο άθροισμα υποπίνακα για το ~i~-οστό ερώτημα.

Παράδειγμα 1

Είσοδος:

3
5
1 -1 1 -1 2
8
-1 2 4 -3 5 2 -5 2
4
-1 -2 -1 -2

Έξοδος:

2
10
0

Περιορισμοί

• ~1 \leq T \leq 25~
• ~1 \leq N \leq 1,000,000~
• Το άθροισμα των ~N~ σε κάθε αρχείο δε θα ξεπερνάει την μέγιστη δυνατή τιμή του ~N~
• ~ |\alpha_i| \leq 10^9 ~
• Το άθροισμα οποιουδήποτε υποπίνακα δεν ξεπερνάει το ~\pm 10^9~
• Όριο χρόνου : 1sec
• Όριο μνήμης : 64MB

Υποπεριπτώσεις

• Για ~20%~ της βαθμολογίας, ~1 \leq N \leq 500~
• Για ~50%~ της βαθμολογίας, ~1 \leq N \leq 5,000~