0297 - SecvSumMax: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 29: Line 29:
: 4 8
: 4 8


== Exemplu ==
== Exemplu 2 ==
; Intrare
; Intrare
: secvsummax.out
: secvsummax.out
Line 35: Line 35:
: -1 2 3 -10 2 8 5 8 4  
: -1 2 3 -10 2 8 5 8 4  
; Ieșire
; Ieșire
: secvsummax.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.


Line 44: Line 43:
# 0297 - SecvSumMax
# 0297 - SecvSumMax


def citire():
def validate_input(n, nums):
     try:
     if not (1 <= n <= 100000):
        n = int(input())
         return False
         a = []
    if len(nums) != n:
        for i in range(n):
         return False
            a.extend(list(map(int, input().split())))
     if all(num <= 0 for num in nums):
         return a
         return False
     except:
    return True
         print("Datele nu corespund restricțiilor impuse.")
        return []


def secvsummax(a):
def find_max_subsequence(n, nums):
     max_sum = a[0]
     if not validate_input(n, nums):
        return "Datele nu corespund restricțiilor impuse."
   
     start, end = 0, 0
     start, end = 0, 0
     curr_sum = a[0]
     max_sum = 0
     curr_start = 0
     current_sum = 0
     for i in range(1, len(a)):
 
         if curr_sum < 0:
     for i in range(n):
            curr_sum = a[i]
         current_sum += nums[i]
             curr_start = i
        if current_sum > max_sum:
        else:
             max_sum = current_sum
             curr_sum += a[i]
             end = i
         if curr_sum > max_sum or (curr_sum == max_sum and i - curr_start < end - start):
         if current_sum < 0:
             max_sum = curr_sum
             current_sum = 0
             start, end = curr_start, i
             start = i + 1
     return start+1, end+1
 
     return f"{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__":
if __name__ == "__main__":
     a = citire()
     file_name = "secvsummax.in"
    if a:
    with open(file_name, "r") as file:
         start, end = secvsummax(a)
         n = int(file.readline())
         if validare(a, start, end):
        nums = []
             print("Datele sunt introduse corect.")
         for _ in range(n):
            print(start, end)
             nums.extend(map(int, file.readline().split()))
        else:
            print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele nu corespund restricțiilor impuse.")


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


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== 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.
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:
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.
 
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."


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.
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.


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.
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.


Î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".
__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

Revision as of 21:17, 14 May 2023

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