4241 - max2secv: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4241/max2secv - max2secv] ---- Se dă un șir a1, a2, …, an de numere întregi. Definim suma unei secvențe ai, ai+1, …, aj ca fiind suma elementelor sale, adică ai + ai+1 + ... + aj. == Cerinţa == Să se determine suma maximă posibilă care se poate obține din două secvențe disjuncte din șir. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații....
 
Flaviu (talk | contribs)
No edit summary
 
(2 intermediate revisions by the same user not shown)
Line 13: Line 13:


== Date de ieșire ==  
== Date de ieșire ==  
Programul va afișa pe ecran numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte.
Dacă datele sunt introduse corect, pe ecran se va afișa:
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Line 19: Line 20:
* -100 ≤ a[i] ≤ 100
* -100 ≤ a[i] ≤ 100
* Două secvențe sunt disjuncte dacă nu au niciun element comun.
* Două secvențe sunt disjuncte dacă nu au niciun element comun.
== Exemplu ==
== Exemplu 1 ==
; Intrare
; Intrare
: 6
: 6
: 2 -1 3 -8 4 -5
: 2 -1 3 -8 4 -5
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: 8
: 8
== Exemplu 2 ==
; Intrare
: 1 2 3
: 77
; Ieșire
: Datele nu corespund restricțiilor impuse.


== Rezolvare ==  
== Rezolvare ==  
Line 31: Line 41:
# 4241 - max2secv
# 4241 - max2secv


def citire_lista():
def validate_input(n, nums):
     n = int(input())
     if not (2 <= n <= 100000):
     lista = list(map(int, input().split()))
        return False
     return lista
     if len(nums) != n:
        return False
    if any(num < -100 or num > 100 for num in nums):
        return False
     return True


def find_max_sum(n, nums):
    if not validate_input(n, nums):
        return "Datele nu corespund restricțiilor impuse."


def suma_maxima(lista):
    max_sum = float('-inf')
    # Calculăm suma maximă a unei secvențe care se termină în fiecare poziție
     for i in range(n-1):
    sume_maxime_stanga = [lista[0]]
         sum1 = sum(nums[:i+1])
     for i in range(1, len(lista)):
        sum2 = sum(nums[i+1:])
         sume_maxime_stanga.append(max(lista[i], sume_maxime_stanga[i-1]+lista[i]))
        max_sum = max(max_sum, sum1 + sum2)
   
    return max_sum


    # Calculăm suma maximă a unei secvențe care începe din fiecare poziție
if __name__ == "__main__":
     sume_maxime_dreapta = [lista[-1]]
     n = int(input())
     for i in range(len(lista)-2, -1, -1):
     nums = list(map(int, input().split()))
        sume_maxime_dreapta.insert(0, max(lista[i], sume_maxime_dreapta[0]+lista[i]))


     # Determinăm suma maximă dintre cele două secvențe disjuncte
     result = find_max_sum(n, nums)
    suma_maxima = sume_maxime_stanga[-1]  # suma întregului șir
    print(result)
    for i in range(len(lista)-1):
        suma_maxima = max(suma_maxima, sume_maxime_stanga[i]+sume_maxime_dreapta[i+1])


    return suma_maxima


</syntaxhighlight>
== Explicatie Rezolvare ==
validate_input(n, nums): Această funcție primește numărul n și lista nums și verifică dacă datele de intrare sunt valide în conformitate cu restricțiile cerinței. Verificările efectuate sunt:


def validare(lista, suma_maxima):
Verifică dacă n se află în intervalul [2, 100000]. Dacă nu, funcția returnează False.
    # verificăm că suma maximă poate fi obținută din două secvențe disjuncte
Verifică dacă lungimea listei nums este egală cu n. Dacă nu, funcția returnează False.
    for i in range(1, len(lista)):
Verifică dacă există cel puțin un element în lista nums care nu se încadrează în intervalul [-100, 100]. Dacă da, funcția returnează False.
        # verificăm că suma maximă a unei secvențe care se termină în i este mai mică sau egală decât suma maximă a unei secvențe care se termină în i-1
Dacă toate verificările sunt îndeplinite, funcția returnează True, semnalând că datele sunt valide.
        if sum(lista[:i]) <= sum(lista[:i-1]):
find_max_sum(n, nums): Această funcție primește numărul n și lista nums și determină suma maximă care se poate obține din două secvențe disjuncte din șir. Funcția inițializează max_sum cu o valoare extrem de mică (pentru a permite compararea și actualizarea corectă).
            continue
        for j in range(i+1, len(lista)):
            # verificăm că suma maximă a unei secvențe care începe din j este mai mică sau egală decât suma maximă a unei secvențe care începe din j+1
            if sum(lista[j:]) <= sum(lista[j+1:]):
                continue
            if sum(lista[:i]) + sum(lista[j:]) == suma_maxima:
                return True
    return False
 


if __name__ == "__main__":
Apoi, folosind o buclă for de la 0 la n-2, se calculează suma primelor i+1 elemente (sum1) și suma ultimelor n-i-1 elemente (sum2). Suma acestor două secvențe este calculată ca sum1 + sum2, iar rezultatul este actualizat dacă această sumă este mai mare decât max_sum. Astfel, se determină suma maximă posibilă.
    lista = citire_lista()
    s = suma_maxima(lista)
    if validare(lista, s):
        print(s)
    else:
        print("Nu se poate obține suma maximă din două secvențe disjuncte.")


</syntaxhighlight>
La final, funcția returnează max_sum, reprezentând suma maximă a două secvențe disjuncte.
== Explicatie Rezolvare ==
Funcția citire_lista() primește șirul de numere de la tastatură și îl returnează sub formă de listă.


Funcția suma_maxima(lista) determină suma maximă posibilă care se poate obține din două secvențe disjuncte din șir. Pentru aceasta, calculează suma maximă a unei secvențe care se termină în fiecare poziție a șirului și suma maximă a unei secvențe care începe din fiecare poziție a șirului, folosind metoda Kadane. Apoi, determină suma maximă dintre două secvențe disjuncte din șir, parcurgând
__main__: Această secțiune verifică dacă scriptul este executat direct (nu importat ca modul) și conține citirea datelor de intrare de la tastatură și apelarea funcției find_max_sum.

Latest revision as of 21:18, 14 May 2023

Sursa: - max2secv


Se dă un șir a1, a2, …, an de numere întregi. Definim suma unei secvențe ai, ai+1, …, aj ca fiind suma elementelor sale, adică ai + ai+1 + ... + aj.


Cerinţa[edit | edit source]

Să se determine suma maximă posibilă care se poate obține din două secvențe disjuncte din șir.


Date de intrare[edit | edit source]

Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații.


Date de ieșire[edit | edit source]

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări[edit | edit source]

  • 2 ≤ n ≤ 100.000
  • -100 ≤ a[i] ≤ 100
  • Două secvențe sunt disjuncte dacă nu au niciun element comun.

Exemplu 1[edit | edit source]

Intrare
6
2 -1 3 -8 4 -5
Ieșire
Datele sunt introduse correct.
8

Exemplu 2[edit | edit source]

Intrare
1 2 3
77
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare[edit | edit source]

Rezolvare ver. 1[edit | edit source]

<syntaxhighlight lang="python" line>

  1. 4241 - max2secv

def validate_input(n, nums):

   if not (2 <= n <= 100000):
       return False
   if len(nums) != n:
       return False
   if any(num < -100 or num > 100 for num in nums):
       return False
   return True

def find_max_sum(n, nums):

   if not validate_input(n, nums):
       return "Datele nu corespund restricțiilor impuse."
   max_sum = float('-inf')
   for i in range(n-1):
       sum1 = sum(nums[:i+1])
       sum2 = sum(nums[i+1:])
       max_sum = max(max_sum, sum1 + sum2)
   
   return max_sum

if __name__ == "__main__":

   n = int(input())
   nums = list(map(int, input().split()))
   result = find_max_sum(n, nums)
   print(result)


</syntaxhighlight>

Explicatie Rezolvare[edit | edit source]

validate_input(n, nums): Această funcție primește numărul n și lista nums și verifică dacă datele de intrare sunt valide în conformitate cu restricțiile cerinței. Verificările efectuate sunt:

Verifică dacă n se află în intervalul [2, 100000]. Dacă nu, funcția returnează False. Verifică dacă lungimea listei nums este egală cu n. Dacă nu, funcția returnează False. Verifică dacă există cel puțin un element în lista nums care nu se încadrează în intervalul [-100, 100]. Dacă da, funcția returnează False. Dacă toate verificările sunt îndeplinite, funcția returnează True, semnalând că datele sunt valide. find_max_sum(n, nums): Această funcție primește numărul n și lista nums și determină suma maximă care se poate obține din două secvențe disjuncte din șir. Funcția inițializează max_sum cu o valoare extrem de mică (pentru a permite compararea și actualizarea corectă).

Apoi, folosind o buclă for de la 0 la n-2, se calculează suma primelor i+1 elemente (sum1) și suma ultimelor n-i-1 elemente (sum2). Suma acestor două secvențe este calculată ca sum1 + sum2, iar rezultatul este actualizat dacă această sumă este mai mare decât max_sum. Astfel, se determină suma maximă posibilă.

La final, funcția returnează max_sum, reprezentând suma maximă a două secvențe disjuncte.

__main__: Această secțiune verifică dacă scriptul este executat direct (nu importat ca modul) și conține citirea datelor de intrare de la tastatură și apelarea funcției find_max_sum.