3959 - MaxSecvK

Cerința

Se consideră un șir A de n numere întregi. Pentru fiecare subsecvență de lungimea k să se afișeze valoarea maximă.

Date de intrare

Fișierul de intrare maxsecvk.in conține pe prima linie două numere naturale nenule n și k, iar pe a doua linie n numere întregi separate prin spații.

Date de ieșire

Fișierul de ieșire maxsecvk.out va conține n–k+1 numere întregi ce reprezintă valoarea maximă a tuturor secvențelor de lungime k.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ k ≤ n
-1.000.000.000 ≤ Ai ≤ -1.000.000.000
prin secvență înțelegem elemente aflate pe poziții consecutive în șir

Exemplu:

maxsecvk.in

9 3

1 2 4 1 3 6 3 2 5

maxsecvk.out

4 4 4 6 6 6 5

Explicație

Se vor afișa 7 numere. Maximul secvenței 1 2 4 este 4 Maximul secvenței 2 4 1 este 4 Maximul secvenței 4 1 3 este 4 Maximul secvenței 1 3 6 este 6 Maximul secvenței 3 6 3 este 6 Maximul secvenței 6 3 2 este 6 Maximul secvenței 3 2 5 este 5

Rezolvare

Definim o functie care preia numele fisierelor de intrare si iesire ca argumente

def max_subsequence(filename_in, filename_out):

   # Deschidem fisierul de intrare pentru citire
   with open(filename_in, 'r') as file:
       # Citim prima linie si o impartim in doua numere, n si k
       n, k = map(int, file.readline().split())
       # Citim a doua linie, o impartim in numere si le stocam intr-o lista
       numbers = list(map(int, file.readline().split()))

   # Calculam valoarea maxima pentru fiecare subsecventa de lungime k
   max_values = [max(numbers[i:i+k]) for i in range(n-k+1)]

   # Deschidem fisierul de iesire pentru scriere
   with open(filename_out, 'w') as file:
       # Scriem fiecare valoare maxima in fisier, separate prin spatii
       for value in max_values:
           file.write(str(value) + ' ')

Apelam functia cu numele fisierelor de intrare si iesire

max_subsequence('maxsecvk.in', 'maxsecvk.out')

</syntaxhighlight>