Editing 4266 - MITM

== Cerinta ==

Fie un număr natural s și un șir de n numere naturale nenule. Să se determine suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.

== Date de intrare ==

Programul citește de la tastatură numărul n și s, apoi n numere naturale, separate prin spații, reprezentând elementele șirului.

== Date de iesire ==

Programul va afișa pe ecran numărul M, reprezentând suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.

== Restrictii si precizari ==

*3 ≤ n ≤ 40
*1 ≤ s ≤ 2.000.000.000
*Șirul va conține numere naturale nenule mai mici decât 50.000.001.
*Toate elementele șirului vor fi mici sau egale decât s.

== Exemplul 1 ==
;Intrare
:5 20
:5 10 6 8 3

;Iesire
;Datele introduse corespund restrictiilor impuse
:19

== Exemplul 2 ==
;Intrare
:1 1
:4 29 2 0
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def suma_maxima_subsir(n, s, sir):
    stanga = 0
    suma_curenta = 0
    suma_maxima = 0

    for dreapta in range(n):
        suma_curenta += sir[dreapta]

        while suma_curenta > s:
            suma_curenta -= sir[stanga]
            stanga += 1

        suma_maxima = max(suma_maxima, suma_curenta)

    return suma_maxima

def main():
    # Citire număr de elemente și suma s
    n, s = map(int, input("Introduceti n si s: ").split())

    # Citire elemente șirului
    sir = list(map(int, input("Introduceti n numere separate prin spatii: ").split()))

    # Calcul și afișare rezultat
    rezultat = suma_maxima_subsir(n, s, sir)
    print("Suma maximă posibilă este:", rezultat)

if __name__ == "__main__":
    main()

</syntaxhighlight>

== Explicatie ==

Suma maximă mai mică sau egală decât 20 este 17 și se formează doar din numărul 17.