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

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.