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

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

# 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.")

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