3844 - KSum

Sursa: 3844 - KSum

---

Cerinţa

După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K 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. A zis să vă întrebe pe voi cum se face.

Date de intrare

Fișierul de intrare ksum.in conține pe prima linie numerele N și K, pe următoarea linie N elemente întregi reprezentând elementele vectorului.

Date de ieșire

Fișierul de ieșire ksum.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.

Restricţii şi precizări

• 1 ≤ K <= n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].

Exemplu

Intrare

6 3

5 4 -10 1 2 3

Ieșire

6

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 3844 - KSum

def citeste_date_intrare():

   n = int(input())
   sir = []
   for i in range(n):
       sir.append(int(input()))
   return sir

def numara_secvente_crescatoare(sir):

   numar_secvente = 0
   lungime_maxima = 1
   lungime_curenta = 1
   for i in range(1, len(sir)):
       if sir[i] >= sir[i-1]:
           lungime_curenta += 1
       else:
           if lungime_curenta > lungime_maxima:
               lungime_maxima = lungime_curenta
               numar_secvente = 1
           elif lungime_curenta == lungime_maxima:
               numar_secvente += 1
           lungime_curenta = 1
   if lungime_curenta > lungime_maxima:
       lungime_maxima = lungime_curenta
       numar_secvente = 1
   elif lungime_curenta == lungime_maxima:
       numar_secvente += 1
   return numar_secvente

def valideaza(sir, numar_secvente):

   assert len(sir) > 0
   assert numar_secvente >= 0

if __name__ == "__main__":

   sir = citeste_date_intrare()
   numar_secvente = numara_secvente_crescatoare(sir)
   valideaza(sir, numar_secvente)
   print(numar_secvente)

</syntaxhighlight>

Explicatie Rezolvare

Pentru a rezolva această problemă, putem utiliza o metodă numită "maximum subarray problem", care constă în găsirea subsecvenței continue a unui șir dat, care are cea mai mare sumă. Putem utiliza o variantă a algoritmului Kadane, care funcționează în timp liniar.