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

<syntaxhighlight lang="python" line>

1. 0134 - SecvK

1. citim valorile de n și k

n, k = map(int, input().split())

1. citim șirul de numere

a = list(map(int, input().split()))

1. 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]

1. 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]

1. afișăm secvența cu suma maximă

print(*max_seq)

</syntaxhighlight>