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: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate, 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 ≤ 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 1

Intrare

secvsummax.out

10

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

Ieșire

secvsummax.out

Datele sunt introduse correct.

4 8

Exemplu 2

Intrare

secvsummax.out

67

-1 2 3 -10 2 8 5 8 4

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 0297 - SecvSumMax

def validate_input(n, nums):

   if not (1 <= n <= 100000):
       return False
   if len(nums) != n:
       return False
   if all(num <= 0 for num in nums):
       return False
   return True

def find_max_subsequence(n, nums):

   if not validate_input(n, nums):
       return "Datele nu corespund restricțiilor impuse."
   
   start, end = 0, 0
   max_sum = 0
   current_sum = 0

   for i in range(n):
       current_sum += nums[i]
       if current_sum > max_sum:
           max_sum = current_sum
           end = i
       if current_sum < 0:
           current_sum = 0
           start = i + 1

   return f"{start + 1} {end + 1}"

if __name__ == "__main__":

   file_name = "secvsummax.in"
   with open(file_name, "r") as file:
       n = int(file.readline())
       nums = []
       for _ in range(n):
           nums.extend(map(int, file.readline().split()))

   result = find_max_subsequence(n, nums)
   print(result)

</syntaxhighlight>

Explicatie Rezolvare

validate_input(n, nums): Această funcție primește un număr n și o listă nums și validează datele de intrare în conformitate cu restricțiile impuse. Verificările efectuate sunt:

Verifică dacă n se află în intervalul [1, 100000]. Dacă nu se îndeplinește această condiție, funcția returnează False, semnalând că datele nu sunt valide. Verifică dacă lungimea listei nums este egală cu n. Dacă lungimea nu este corectă, funcția returnează False. Verifică dacă toate numerele din lista nums sunt mai mici sau egale cu 0. Dacă există cel puțin un număr mai mare decât 0, funcția returnează False. Dacă toate aceste verificări sunt îndeplinite, funcția returnează True, semnalând că datele de intrare sunt valide. find_max_subsequence(n, nums): Această funcție primește un număr n și o listă nums și aplică algoritmul pentru a găsi secvența de elemente cu suma maximă. Funcția începe prin apelarea funcției validate_input pentru a verifica validitatea datelor de intrare. Dacă datele nu sunt valide, funcția returnează mesajul "Datele nu corespund restricțiilor impuse."

Dacă datele sunt valide, funcția inițializează variabilele start, end, max_sum și current_sum cu valorile inițiale 0. Apoi, parcurge lista nums folosind un buclă for și adaugă fiecare element la suma curentă current_sum. Dacă current_sum devine mai mare decât max_sum, actualizează max_sum cu current_sum și actualizează end la poziția curentă. Dacă current_sum devine mai mică decât 0, resetează-o la 0 și actualizează start la poziția curentă + 1.

La finalul buclei, funcția returnează rezultatul sub forma unui șir format din start + 1 și end + 1. Adăugarea valorii 1 este necesară pentru a respecta numerotarea elementelor de la 1 la n.

__main__: Această secțiune verifică dacă scriptul este executat direct (nu importat ca modul) și conține codul de citire a fișierului de intrare și apelarea funcției find_max_subsequence. Mai întâi, se deschide fișierul de intrare secvsummax.in în modul "r" (citire). Se citește prima linie pentru a obține valoarea lui n, iar apoi se citesc următoarele `n