4241 - max2secv: Difference between revisions
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.... |
No edit summary |
||
(2 intermediate revisions by the same user not shown) | |||
Line 13: | Line 13: | ||
== Date de ieșire == | == Date de ieșire == | ||
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 | def validate_input(n, nums): | ||
n = | if not (2 <= n <= 100000): | ||
return False | |||
return | 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]) | |||
for i in range(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 == | |||
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. |
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>
- 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.