4241 - max2secv

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

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.

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

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

Exemplu 1

Intrare

6

2 -1 3 -8 4 -5

Ieșire

Datele sunt introduse correct.

8

Exemplu 2

Intrare

1 2 3

77

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 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)

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.