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 c, 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

Intrare

6

2 -1 3 -8 4 -5

Ieșire

Datele nu corespund restricțiilor impuse.

Datele sunt introduse correct.

8

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 4241 - max2secv

def citire_lista():

   try:
       k = int(input())
       n = int(input())
       lista = list(map(int, input().split()))
       p = int(input())
       return k, lista, p
   except:
       print("Datele nu corespund restrictiilor impuse.")
       return None

def rezolva(k, lista):

   try:
       # calculam dictionarul frecventelor
       frecvente = {}
       for element in lista:
           frecvente[element] = frecvente.get(element, 0) + 1
       
       # gasim elementul cu cea mai mare frecventa
       max_frecventa = max(frecvente.values())
       element_max_frecventa = max(k for k, v in frecvente.items() if v == max_frecventa)
       
       # calculam lungimea maxima a unui platou dupa k operatii
       lungime_maxima = min(max_frecventa + k, len(lista))
       return lungime_maxima if p == 1 else element_max_frecventa
   except:
       print("Datele nu corespund restrictiilor impuse.")
       return None

def valideaza(valoare):

   try:
       if valoare is not None:
           print("Datele sunt introduse corect.")
           print(valoare)
       else:
           print("Datele nu corespund restrictiilor impuse.")
   except:
       print("Datele nu corespund restrictiilor impuse.")

if __name__ == "__main__":

   lista_intrare = citire_lista()
   if lista_intrare is not None:
       k, lista, p = lista_intrare
       rezultat = rezolva(k, lista)
       valideaza(rezultat)

</syntaxhighlight>

Explicatie Rezolvare

citire_lista(): această funcție încearcă să citească o listă de întregi și două valori întregi k și p de la tastatură. Dacă citirea este corectă, funcția returnează k, lista și p. În caz contrar, afișează un mesaj de eroare "Datele nu corespund restrictiilor impuse." și returnează None.

rezolva(k, lista): această funcție primește două argumente: k (un întreg) și lista (o listă de întregi). Scopul acestei funcții este să găsească lungimea maximă a unui platou după k operații. Un platou este o secvență de elemente consecutive egale din lista dată. Operațiile sunt de două tipuri: (1) adăugarea unui element la lista dată, (2) eliminarea unui element din lista dată. Funcția încearcă să calculeze elementul din lista cu cea mai mare frecvență și să găsească lungimea maximă a unui platou după k operații. Dacă p = 1, funcția returnează elementul cu cea mai mare frecvență, altfel returnează lungimea maximă a unui platou.

valideaza(valoare): această funcție primește o valoare (fie un întreg, fie o listă de întregi) și afișează un mesaj "Datele sunt introduse corect." și valoarea dată pe un rând separat. Dacă valoarea dată nu este un întreg sau o listă de întregi, afișează un mesaj de eroare "Datele nu corespund restrictiilor impuse.".

În secțiunea principală a codului, se citesc datele de intrare folosind funcția citire_lista() și se apelează funcția rezolva() cu argumentele corespunzătoare. Apoi, rezultatul este validat cu funcția valideaza().