0297 - SecvSumMax: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 12: Linia 12:
Fișierul de ieșire secvsummax.out va conține:
Fișierul de ieșire secvsummax.out va conține:
Dacă datele sunt introduse corect, pe ecran se va afișa:  
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."'''.
'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Linia 19: Linia 19:
* dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
* dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
* șirul va conține cel puțin un element pozitiv
* șirul va conține cel puțin un element pozitiv
== Exemplu ==
== Exemplu 1 ==
; Intrare
; Intrare
: secvsummax.out
: 10
: 10
: -4 1 -5 1 4 -2 2 3 -4 4
: -4 1 -5 1 4 -2 2 3 -4 4
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: secvsummax.out
: Datele sunt introduse correct.
: Datele sunt introduse correct.
: 4 8
: 4 8
== Exemplu ==
; Intrare
: secvsummax.out
: 67
: -1 2 3 -10 2 8 5 8 4
; Ieșire
: secvsummax.out
: Datele nu corespund restricțiilor impuse.


== Rezolvare ==  
== Rezolvare ==  

Versiunea de la data 3 mai 2023 07:54

Sursa: 0297 - SecvSumMax


Cerinţa

Se dă un șir cu n elemente, numere întregi. Determinați secvența de elemente cu suma maximă.


Date de intrare

Fișierul de intrare secvsummax.in conține pe prima linie numărul n; urmează cele n elemente ale șirului, dispuse pe mai multe linii și separate prin spații.


Date de ieșire

Fișierul de ieșire secvsummax.out va conține: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

  • 1 ≤ n ≤ 100.000
  • elementele șirului vor avea cel mult 4 cifre și sunt numerotate de la 1 la n
  • dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
  • șirul va conține cel puțin un element pozitiv

Exemplu 1

Intrare
secvsummax.out
10
-4 1 -5 1 4 -2 2 3 -4 4
Ieșire
secvsummax.out
Datele sunt introduse correct.
4 8

Exemplu

Intrare
secvsummax.out
67
-1 2 3 -10 2 8 5 8 4
Ieșire
secvsummax.out
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

# 0297 - SecvSumMax

def citire():
    try:
        n = int(input())
        a = []
        for i in range(n):
            a.extend(list(map(int, input().split())))
        return a
    except:
        print("Datele nu corespund restricțiilor impuse.")
        return []

def secvsummax(a):
    max_sum = a[0]
    start, end = 0, 0
    curr_sum = a[0]
    curr_start = 0
    for i in range(1, len(a)):
        if curr_sum < 0:
            curr_sum = a[i]
            curr_start = i
        else:
            curr_sum += a[i]
        if curr_sum > max_sum or (curr_sum == max_sum and i - curr_start < end - start):
            max_sum = curr_sum
            start, end = curr_start, i
    return start+1, end+1

def validare(a, start, end):
    return sum(a[start-1:end]) == max(sum(a[i:j]) for i in range(len(a)) for j in range(i+1,len(a)+1))

if __name__ == "__main__":
    a = citire()
    if a:
        start, end = secvsummax(a)
        if validare(a, start, end):
            print("Datele sunt introduse corect.")
            print(start, end)
        else:
            print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele nu corespund restricțiilor impuse.")

Explicatie Rezolvare

Pentru a rezolva această problemă putem folosi algoritmul Kadane, care constă în a parcurge șirul și a calcula suma maximă a unei subsecvențe care se termină la fiecare element. De asemenea, menținem și pozițiile de început și sfârșit ale acestei subsecvențe. La fiecare pas, dacă suma calculată este mai mare decât suma maximă anterioră, actualizăm pozițiile de început și sfârșit ale subsecvenței cu suma maximă. La final, returnăm aceste poziții. Funcția citire citește datele de intrare, formate din n următoarele linii, fiecare conținând o valoare din șir. Lista a este construită prin extinderea sub-listelor formate din aceste valori.

Funcția secvsummax primește lista a și returnează pozițiile de început și sfârșit ale subsecvenței cu suma maximă, conform algoritmului Kadane.

Funcția validare primește lista a și pozițiile de început și sfârșit ale unei subsecvențe și returnează True dacă această subsecvență are suma maximă și False în caz contrar.

În funcția principală, se apelează funcția citire, apoi se determină subsecvența cu suma maximă cu ajutorul funcției secvsummax. Dacă această subsecvență este validă, se afișează pozițiile de început și sfârșit, altfel se afișează "Eroare".