Editing 3846 - KSum2

Sursa: [https://www.pbinfo.ro/probleme/3846/ksum2 3846 - KSum2]
----
== Cerinţa ==
După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N, K și W 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 și cel mult W. A zis să vă întrebe pe voi cum se face.


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


== Date de ieșire == 
Fișierul de ieșire ksum2.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 și cel mult W.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000
* elementele şirului vor avea cel mult 4 cifre
* o secvență cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător
== Exemplu ==
; Intrare
: 8: 
: 12 10 15 17 17
: 10 12 14
; Ieșire
: 3

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3846 - KSum2

def read_input():
    with open("ksum2.in", "r") as fin:
        n, k, w = map(int, fin.readline().split())
        v = list(map(int, fin.readline().split()))
        return n, k, w, v

def solve(n, k, w, v):
    max_sum = [0] * n
    current_sum = 0
    for i in range(n):
        current_sum += v[i]
        if i >= k:
            current_sum -= v[i - k]
        if i >= k - 1:
            max_sum[i] = max(max_sum[i - 1], current_sum)
        else:
            max_sum[i] = current_sum
        if i >= w:
            current_sum -= v[i - w]
            if current_sum + max_sum[i - w] > max_sum[i]:
                max_sum[i] = current_sum + max_sum[i - w]
    return max_sum[n - 1]

def validate_output(output_file, result):
    with open(output_file, "r") as fin:
        expected_result = int(fin.readline().strip())
        return result == expected_result

if __name__ == "__main__":
    n, k, w, v = read_input()
    result = solve(n, k, w, v)
    is_valid = validate_output("ksum2.out", result)
    print(result)
    print("Result is valid:", is_valid)


</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru rezolvarea acestei probleme putem adapta algoritmul lui Kadane pentru a căuta suma maximă a unei secvențe de lungime cel puțin K și cel mult W.

Putem folosi o listă auxiliară max_sum în care vom memora suma maximă până la fiecare element din vector. În mod similar cu algoritmul lui Kadane, dacă suma până la un anumit element este negativă, o vom ignora și vom începe o nouă secvență de la acel element.

Diferența constă în faptul că trebuie să verificăm la fiecare pas dacă am ajuns la un element din intervalul [K, W], iar în acest caz, dacă suma maximă până la acel element este mai mare decât suma maximă găsită anterior, vom actualiza această valoare.

În final, vom returna suma maximă găsită pentru o secvență de lungime cel puțin K și cel mult W.