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

<syntaxhighlight lang="python" line>

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

</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