24ος ΠΔΠ Καμπ (κοινά)
Άθροισμα υπακολουθίας (maxksum)

Δίνεται μια ακολουθία \(N\) ακεραίων αριθμών (αρνητικών, θετικών ή και μηδέν) και ένας φυσικός αριθμός \(K\), \(1 \leq K \leq N\). Ζητείται η μέγιστη τιμή του αθροίσματος \(K\) ή λιγότερων διαδοχικών όρων της ακολουθίας.

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

Η πρώτη γραμμή της εισόδου θα περιέχει τους δύο ακέραιους αριθμούς \(N\) και \(K\), χωρισμένους με ένα κενό διάστημα. Η δεύτερη γραμμή θα περιέχει τους \(N\) ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα.

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

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό: τη μέγιστη τιμή του αθροίσματος \(K\) ή λιγότερων διαδοχικών όρων της ακολουθίας.

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

1^o

maxksum.in	maxksum.out
10 6 1 10 -1 -1 4 -8 7 2 -1 4	13

2^o

maxksum.in	maxksum.out
10 4 1 7 -10 -11 9 9 -7 2 12 -4	18

3^o

maxksum.in	maxksum.out
4 2 -1 -1 -1 -1	0

Εξήγηση παραδειγμάτων: Με έντονα γράμματα στα παραδείγματα φαίνονται οι όροι της ακολουθίας που δίνουν το μέγιστο άθροισμα. Στο τρίτο παράδειγμα το μέγιστο άθροισμα επιτυγχάνεται αν δεν αθροίσουμε κανέναν όρο της ακολουθίας, αφού είναι όλοι αρνητικοί.

Περιορισμοί:

• \(2 \leq N \leq 1.000.000\).
• \(1 \leq K \leq N\).
• Οι αριθμοί της ακολουθίας θα έχουν απόλυτη τιμή το πολύ ίση με \(30.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(16\) MB.