Editing 4241 - max2secv

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.


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

== 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 ==
; Intrare
: 6
: 2 -1 3 -8 4 -5
; Ieșire
: 8

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 4241 - max2secv

def citire_lista():
    n = int(input())
    lista = list(map(int, input().split()))
    return lista


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

    # Calculăm suma maximă a unei secvențe care începe din fiecare poziție
    sume_maxime_dreapta = [lista[-1]]
    for i in range(len(lista)-2, -1, -1):
        sume_maxime_dreapta.insert(0, max(lista[i], sume_maxime_dreapta[0]+lista[i]))

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

    return suma_maxima


def validare(lista, suma_maxima):
    # verificăm că suma maximă poate fi obținută din două secvențe disjuncte
    for i in range(1, len(lista)):
        # 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
        if sum(lista[:i]) <= sum(lista[:i-1]):
            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__":
    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>
== 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