Editing 3937 - KSum3

Sursa: [https://www.pbinfo.ro/probleme/3937/ksum3 3937 - KSum3]
----
== Cerinţa ==
Se dă N și un vector de N elemente numere întregi, găsiți suma maximă a unei subsecvențe (elemente adiacente) cu lungimile cuprinse între K și W (K <= lungime <= W).


== Date de intrare ==
Programul citește de la tastatură numerele N, K, W iar apoi un vector de N numere întregi.


== Date de ieșire == 
Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul S, reprezentând suma maxima a unei subsecvențe care respectă condițiile din enunț'', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

== Restricţii şi precizări ==
* 1 ≤ K ≤ W ≤ N ≤ 1.000.000
* cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000].crescător
== Exemplu 1 ==
; Intrare
: 6 3 4
: 5 4 -10 1 2 3
; Ieșire
: Datele sunt introduse correct.
: 6

== Exemplu 1 ==
; Intrare
: 256
: 5 4 -10 -3 -3 0 0 0 
; Ieșire
: Datele nu corespund restricțiilor impuse.


== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3937 - KSum3

def validate_input(N, K, W, arr):
    if not (1 <= K <= W <= N <= 1000000):
        return False
    if len(arr) != N:
        return False
    if any(num < -1000000000 or num > 1000000000 for num in arr):
        return False
    return True


def find_max_subsequence_sum(N, K, W, arr):
    if not validate_input(N, K, W, arr):
        return "Datele nu corespund restricțiilor impuse."

    max_sum = float("-inf")
    current_sum = 0

    for i in range(N):
        current_sum += arr[i]
        if i >= K - 1:
            max_sum = max(max_sum, current_sum)
            current_sum -= arr[i - K + 1]

    return max_sum


if __name__ == "__main__":
    N = int(input("Introduceti N: "))
    K = int(input("Introduceti K: "))
    W = int(input("Introduceti W: "))

    arr = list(map(int, input("Introduceti vectorul de numere întregi: ").split()))

    result = find_max_subsequence_sum(N, K, W, arr)
    print(result)


</syntaxhighlight>
== Explicatie Rezolvare ==
validate_input(N, K, W, arr): Această funcție primește patru parametri: N, K, W și arr, reprezentând numărul de elemente, limitele K și W, și lista de numere întregi arr. Scopul acestei funcții este să valideze datele de intrare conform restricțiilor impuse. Verificările includ:

Dacă K și W sunt în intervalul permis, adică 1 <= K <= W <= N <= 1000000.
Dacă lungimea listei arr este egală cu N.
Dacă oricare dintre numerele din lista arr depășește limitele [-1000000000, 1000000000].
Dacă oricare dintre aceste condiții nu este îndeplinită, funcția returnează False, indicând că datele nu corespund restricțiilor. În caz contrar, funcția returnează True, semnificând că datele sunt introduse corect.

find_max_subsequence_sum(N, K, W, arr): Această funcție primește aceiași parametri ca și validate_input: N, K, W și arr. Scopul acestei funcții este să găsească suma maximă a unei subsecvențe cu lungimi cuprinse între K și W în lista arr. Funcția verifică întâi datele de intrare utilizând funcția validate_input. Dacă datele nu sunt valide, funcția returnează mesajul "Datele nu corespund restricțiilor impuse."

Dacă datele sunt valide, funcția inițializează max_sum cu o valoare negativă foarte mică și current_sum cu 0. Apoi, utilizează o buclă for pentru a itera prin lista arr. La fiecare pas, adaugă elementul curent la suma curentă current_sum. Dacă indicele curent i este mai mare sau egal cu K - 1, înseamnă că lungimea subsecvenței este cel puțin K, așa că compară current_sum cu max_sum și actualizează max_sum dacă este necesar. În final, se scade elementul din subsecvență care nu mai face parte din fereastra curentă, adică arr[i - K + 1], din current_sum.

La sfârșit, funcția returnează max_sum, care reprezintă suma maximă a subsecvenței.

if __name__ == "__main__": : Acesta este blocul principal al programului care va fi executat doar atunci când scriptul este rulat direct și nu importat ca modul în altă parte a codului. În acest bloc, se face citirea datelor utilizând funcția input() și map(), apoi se apelează funcția find_max_subsequence_sum