3844 - KSum

Sursa: 3844 - KSum

---

Cerinţa

După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K. A zis să vă întrebe pe voi cum se face.

Date de intrare

Fișierul de intrare ksum.in conține pe prima linie numerele N și K, pe următoarea linie N elemente întregi reprezentând elementele vectorului.

Date de ieșire

Fișierul de ieșire ksum.out va conține pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K.

Restricţii şi precizări

• 1 ≤ K <= W <= n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].

Exemplu

Intrare

6 3 4

5 4 -10 1 2 3

Ieșire

6

Rezolvare

Rezolvare ver. 1

# 3844 - KSum

def read_input_file():
    with open("ksum.in", "r") as input_file:
        n, k = map(int, input_file.readline().split())
        v = list(map(int, input_file.readline().split()))
        return n, k, v

def ksum(n, k, v):
    s = [0] * (n + 1)
    for i in range(1, n + 1):
        s[i] = s[i-1] + v[i-1]
    m = [0] * (n + 1)
    for i in range(k, n + 1):
        m[i] = max(m[i-1], s[i] - s[i-k])
    return max(m)

def write_output_file(result):
    with open("ksum.out", "w") as output_file:
        output_file.write(str(result))

if __name__ == '__main__':
    n, k, v = read_input_file()
    result = ksum(n, k, v)
    write_output_file(result)

Explicatie Rezolvare

functia read_input_file citeste datele de intrare din fisier si le returneaza sub forma de tuplu (n, k, v), unde n este numarul de elemente din vector, k este numarul minim de elemente consecutive care trebuie sa fie considerate in calculul sumei, iar v este lista cu elementele vectorului. functia ksum primeste ca parametri n, k si v, si calculeaza suma maxima a unei secvente de lungime cel putin k. Pentru a gasi suma maxima se calculeaza suma elementelor de la 1 la i, pentru fiecare i din vectorul s. De asemenea, se construieste un alt vector, m, care contine pentru fiecare pozitie i din vectorul s, suma maxima a unei secvente de lungime cel putin k care se termina in pozitia i. Suma maxima se va gasi in ultimul element al vectorului m. functia write_output_file scrie rezultatul obtinut in fisierul de iesire. in cadrul if __name__ == '__main__': se apeleaza cele trei functii in ordinea: citirea datelor de intrare, calculul solutiei si scrierea rezultatului in fisierul de iesire.