0134 - SecvK

Sursa: 0134 - SecvK

---

Cerinţa

Se dă un șir cu n numere naturale și un număr k. Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.

Date de intrare

Fişierul de intrare secvk.in conţine pe prima linie numerele n și k, iar pe a doua linie n numere naturale separate prin spaţii.

Date de ieșire

Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.

Restricţii şi precizări

• 1 ≤ k ≤ n ≤ 100.000
• numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 1000
• dacă există mai multe secvențe de lungime k cu suma maximă se va afișa prima

Exemplu

Intrare

8 3

5 6 1 2 6 6 4 3

Ieșire

6 6 4

Rezolvare

Rezolvare ver. 1

# 0134 - SecvK

# citim valorile de n și k
n, k = map(int, input().split())

# citim șirul de numere
a = list(map(int, input().split()))

# calculăm suma primelor k elemente și o considerăm inițial ca fiind suma maximă
max_sum = sum(a[:k])
max_seq = a[:k]

# calculăm suma pentru fiecare secvență de lungime k și păstrăm secvența cu suma maximă
for i in range(n - k):
    seq_sum = sum(a[i+1:i+k+1])
    if seq_sum > max_sum:
        max_sum = seq_sum
        max_seq = a[i+1:i+k+1]

# afișăm secvența cu suma maximă
print(*max_seq)