3937 - KSum3

Sursa: 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

# 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)

Explicatie Rezolvare

validate_input(n, k, w, arr): Această funcție validează datele de intrare. Verifică dacă valorile N, K și W respectă restricțiile impuse și dacă dimensiunea vectorului este în concordanță cu N. Returnează True dacă datele sunt valide și False în caz contrar.

find_max_subsequence_sum(n, k, w, arr): Această funcție calculează suma maximă a unei subsecvențe care respectă condițiile date. Verifică mai întâi validitatea datelor de intrare utilizând funcția validate_input(). Apoi, parcurge vectorul de la stânga la dreapta și, pentru fiecare poziție, calculează suma maximă a unei subsecvențe de lungime cuprinsă între K și W. Returnează suma maximă calculată.

Blocul if __name__ == "__main__": este locul în care se face citirea datelor de intrare și apelarea funcțiilor pentru rezolvarea problemei.

Se deschide fișierul "ksum3.in" pentru citire și se citesc valorile N, K, W de pe prima linie și elementele vectorului de pe a doua linie. Se apelează funcția find_max_subsequence_sum() cu datele citite. Dacă rezultatul returnat este o sumă validă, se afișează "Datele sunt introduse corect." și suma calculată. Altfel, se afișează mesajul "Datele nu corespund restricțiilor impuse."