3846 - KSum2

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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." 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, 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 ≤ 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 1

Intrare

ksum2.in

8

12 10 15 17 17

10 12 14

Ieșire

Datele sunt introduse correct.

ksum2.out

3

Exemplu 1

Intrare

ksum2.in

8

1 2 3 4 5 6

-0,12 123 0 1 -2 -3 1,23

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 3846 - KSum2

def validate_input(N, K, W, arr):
    # Verificăm dacă N, K și W respectă restricțiile
    if not 1 <= N <= 1000 or not 1 <= K <= N or not K <= W <= N:
        return False
    
    # Verificăm dacă elementele din vector respectă restricțiile
    for x in arr:
        if not -9999 <= x <= 9999:
            return False
    
    return True


def max_sequence_sum(arr, K, W):
    # Inițializăm variabilele necesare pentru calculul sumei maxime
    max_sum = -float('inf')
    cur_sum = 0
    start = end = 0
    
    # Parcurgem vectorul și calculăm suma maximă
    for i in range(len(arr)):
        # Adăugăm elementul curent la suma curentă
        cur_sum += arr[i]
        
        # Dacă secvența devine prea lungă, scădem primul element din ea
        if i >= K:
            cur_sum -= arr[i-K]
        
        # Dacă secvența este suficient de lungă, verificăm dacă suma ei este maximă
        if i >= W-1:
            if cur_sum > max_sum:
                max_sum = cur_sum
                start = i-W+1
                end = i
                
        # Dacă suma curentă devine negativă, o resetăm la 0 și mutăm începutul secvenței
        if cur_sum < 0:
            cur_sum = 0
    
    return max_sum


if __name__ == '__main__':
    # Citim datele de intrare
    N, K, W = map(int, input().split())
    arr = list(map(int, input().split()))
    
    # Verificăm dacă datele de intrare sunt corecte
    if not validate_input(N, K, W, arr):
        print('Datele nu corespund restricțiilor impuse.')
    else:
        # Calculăm suma maximă și o afișăm
        max_sum = max_sequence_sum(arr, K, W)
        print(max_sum)

Explicatie Rezolvare

Funcția validate_input primește patru argumente: N, K, W și arr. Această funcție validează datele de intrare pentru a se asigura că ele respectă restricțiile impuse în enunțul problemei. Mai exact, verifică dacă N, K și W se încadrează în intervalul specificat, iar elementele din vectorul arr sunt numere întregi de cel mult patru cifre. Funcția returnează True dacă datele de intrare sunt corecte și False în caz contrar.

Funcția max_sequence_sum primește trei argumente: arr, K și W. Această funcție calculează suma maximă a unei secvențe (elemente adiacente) din vectorul dat, de lungime cel puțin K și cel mult W. Pentru a realiza aceasta, parcurge vectorul dat și calculează suma tuturor secvențelor de lungime între K și W. În timpul parcurgerii, menține suma curentă și, dacă aceasta devine negativă, o resetează la 0 și mută începutul secvenței. Dacă suma curentă depășește maximul anterior, aceasta devine noua sumă maximă. Funcția returnează suma maximă calculată.

În blocul de cod if __name__ == '__main__', se citesc datele de intrare și se apelează funcția validate_input pentru a verifica dacă datele sunt introduse corect. Dacă datele sunt introduse corect, se calculează suma maximă folosind funcția max_sequence_sum și se afișează rezultatul. În caz contrar, se afișează un mesaj de eroare.