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 &les; n &les; 40'''
*'''1 &les; s &les; 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 verificare_date_intrare(n, s, sir):
    if not (3 <= n <= 40 and 1 <= s <= 2000000000):
        return False

    if not all(1 <= x < 50000001 for x in sir):
        return False

    return True

def suma_maxima_subsir(arr, s):
    n = len(arr)
    suma_maxima = 0
    suma_curenta = 0
    stanga = 0

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

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

        suma_maxima = max(suma_maxima, suma_curenta)

    return suma_maxima

# Citire date de intrare
try:
    n = int(input("Introduceți numărul de elemente: "))
    s = int(input("Introduceți suma dorită: "))
    sir = list(map(int, input("Introduceți șirul de numere separate prin spațiu: ").split()))

    # Verificare date de intrare
    if not verificare_date_intrare(n, s, sir):
        raise ValueError("Datele introduse nu corespund restricțiilor impuse.")

    # Calculare și afișare rezultat
    rezultat = suma_maxima_subsir(sir, s)
    print(f"Suma maximă posibilă mai mică sau egală cu {s} este: {rezultat}")

except ValueError as ve:
    print(ve)

</syntaxhighlight>

== Explicatie ==

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