0297 - SecvSumMax

Sursa: 0297 - SecvSumMax

---

Cerinţa

Se dă un șir cu n elemente, numere întregi. Determinați secvența de elemente cu suma maximă.

Date de intrare

Fișierul de intrare secvsummax.in conține pe prima linie numărul n; urmează cele n elemente ale șirului, dispuse pe mai multe linii și separate prin spații.

Date de ieșire

Fișierul de ieșire secvsummax.out va conține pe prima linie numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate.

Restricţii şi precizări

• 1 ≤ n ≤ 100.000
• elementele șirului vor avea cel mult 4 cifre și sunt numerotate de la 1 la n
• dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
• șirul va conține cel puțin un element pozitiv

Exemplu

Intrare

10

-4 1 -5 1 4 -2 2 3 -4 4

Ieșire

4 8

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0297 - SecvSumMax

def citire():

   n = int(input())
   a = []
   for i in range(n):
       a.extend(list(map(int, input().split())))
   return a

def secvsummax(a):

   max_sum = a[0]
   start, end = 0, 0
   curr_sum = a[0]
   curr_start = 0
   for i in range(1, len(a)):
       if curr_sum < 0:
           curr_sum = a[i]
           curr_start = i
       else:
           curr_sum += a[i]
       if curr_sum > max_sum or (curr_sum == max_sum and i - curr_start < end - start):
           max_sum = curr_sum
           start, end = curr_start, i
   return start+1, end+1

def validare(a, start, end):

   return sum(a[start-1:end]) == max(sum(a[i:j]) for i in range(len(a)) for j in range(i+1,len(a)+1))

if __name__ == "__main__":

   a = citire()
   start, end = secvsummax(a)
   if validare(a, start, end):
       print(start, end)
   else:
       print("Eroare")

</syntaxhighlight>

Explicatie Rezolvare

Pentru a rezolva această problemă putem folosi algoritmul Kadane, care constă în a parcurge șirul și a calcula suma maximă a unei subsecvențe care se termină la fiecare element. De asemenea, menținem și pozițiile de început și sfârșit ale acestei subsecvențe. La fiecare pas, dacă suma calculată este mai mare decât suma maximă anterioră, actualizăm pozițiile de început și sfârșit ale subsecvenței cu suma maximă. La final, returnăm aceste poziții. Funcția citire citește datele de intrare, formate din n următoarele linii, fiecare conținând o valoare din șir. Lista a este construită prin extinderea sub-listelor formate din aceste valori.

Funcția secvsummax primește lista a și returnează pozițiile de început și sfârșit ale subsecvenței cu suma maximă, conform algoritmului Kadane.

Funcția validare primește lista a și pozițiile de început și sfârșit ale unei subsecvențe și returnează True dacă această subsecvență are suma maximă și False în caz contrar.

În funcția principală, se apelează funcția citire, apoi se determină subsecvența cu suma maximă cu ajutorul funcției secvsummax. Dacă această subsecvență este validă, se afișează pozițiile de început și sfârșit, altfel se afișează "Eroare".