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

Programul va afișa pe ecran numărul S, reprezentând suma maxima a unei subsecvențe care respectă condițiile din enunț.

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

Intrare

6 3 4

5 4 -10 1 2 3

Ieșire

6

Rezolvare

Rezolvare ver. 1

# 3937 - KSum3

def read_input():
    n, k, w = map(int, input().split())
    array = list(map(int, input().split()))
    return n, k, w, array

def maximum_subarray_sum(n, k, w, array):
    dp = [0] * (n + 1)
    prefix_sum = [0] * (n + 1)
    prefix_sum[0] = array[0]
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i - 1] + array[i]
    for length in range(k, w + 1):
        for i in range(length - 1, n):
            if i == length - 1:
                dp[i] = prefix_sum[i]
            else:
                dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])
    return max(dp[k - 1:n])

def validate_input(n, k, w, array):
    if not (1 <= k <= w <= n <= 1000000):
        return False
    for num in array:
        if not (-1000000000 <= num <= 1000000000):
            return False
    return True

if __name__ == '__main__':
    n, k, w, array = read_input()
    if validate_input(n, k, w, array):
        print(maximum_subarray_sum(n, k, w, array))
    else:
        print("Input is not valid!")

Explicatie Rezolvare

Funcția read_input() citește de la tastatură numerele N, K, W și un vector de N numere întregi și le returnează. Funcția maximum_subarray_sum() primește N, K, W și vectorul citit de la tastatură și returnează suma maximă a unei subsecvențe cu lungimile cuprinse între K și W. Algoritmul folosește programarea dinamică și calculează suma maximă a unei subsecvențe pentru fiecare lungime între K și W. Pe baza acestor calcule se determină suma maximă a întregului vector. Funcția validate_input() primește N, K, W și vectorul citit de la tastatură și verifică dacă acestea respectă condițiile problemei. În funcția principală se citesc datele de intrare, se validează și se apelează funcția de calcul a sumei maxime a unei subsecvențe.