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

def citire():
    n, k = map(int, input().split())
    lst = list(map(int, input().split()))
    return n, k, lst

def secventa_maxima(n, k, lst):
    suma_maxima = 0
    secventa_maxima = []
    for i in range(n-k+1):
        suma = sum(lst[i:i+k])
        if suma > suma_maxima:
            suma_maxima = suma
            secventa_maxima = lst[i:i+k]
    return secventa_maxima

def validare(n, k, lst, secventa):
    assert len(secventa) == k, "Lungimea secventei nu este k"
    assert sum(secventa) == max(sum(lst[i:i+k]) for i in range(n-k+1)), "Suma secventei nu este maxima"
    for x in secventa:
        assert x in lst, "Elementul {} nu se afla in lista initiala".format(x)

if __name__ == "__main__":
    n, k, lst = citire()
    secventa = secventa_maxima(n, k, lst)
    validare(n, k, lst, secventa)
    print(*secventa)

Explicatie Rezolvare

Funcția citire citește datele de intrare și le returnează sub forma unei tuple (n, k, lst). Funcția secventa_maxima calculează secvența de lungime k cu suma maximă din lista lst, utilizând o buclă for și metoda sum. Variabilele suma_maxima și secventa_maxima memorează suma și secvența maximă întâlnită până acum. Funcția validare verifică corectitudinea secvenței calculate de secventa_maxima în raport cu datele de intrare. Funcția verifică lungimea secvenței, suma elementelor și faptul că fiecare element se află în lista inițială. Dacă validarea eșuează, funcția generează o excepție cu un mesaj corespunzător. În if __name__ == "__main__", apelăm funcțiile citire, secventa_maxima și validare, și apoi afișăm secvența maximă utilizând print(*secventa) (acest lucru afișează elementele secvenței separate prin spații, fără paranteze sau alte simboluri).