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 maxsecvkin.txt 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 maxsecvkout.txt 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

Exemplul 1:

maxsecvkin.txt

9 3
1 2 4 1 3 6 3 2 5

maxsecvkout.txt

Datele de intrare corespund restrictiilor impuse
4 4 4 6 6 6 5

Exemplul 2:

maxsecvkin.txt

maxsecvk

maxsecvkout.txt

Datele de intrare nu corespund restrictiilor impuse

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

def validare(nr_n, nr_k, numere):           # functia de validare a datelor de intrare
    if nr_n < 1 or nr_n > 100000 or nr_k < 1 or nr_k > nr_n:
        raise ValueError
    for num in numere:
        if num < -1000000000 or num > 1000000000:
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


def max_subsequence(numere, nr_k):                     # functia de rezolvare
    max_values = [max(numere[i:i + nr_k]) for i in range(len(numere) - nr_k + 1)]
    for value in max_values:
        file_out.write(str(value) + ' ')


if __name__ == '__main__':
    file_in = open('maxsecvkin.txt', 'r')         # declararea fisierelor
    file_out = open('maxsecvkout.txt', 'w')       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        n, k = map(int, file_in.readline().split())
        numbers = list(map(int, file_in.readline().split()))

        validare(n, k, numbers)                 # apelul functiei de validare
        max_subsequence(numbers, k)               # apelul functiei de rezolvare

    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")