1877 - K Max

Cerinta

Se dă un șir cu n elemente, numere întregi, și un număr natural k ≤ n. Calculați cea mai mare sumă care poate fi obținută schimbând semnul a exact k elemente aflate pe poziții distincte din șirul dat.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului, apoi numărul k.

Date de iesire

Programul va afișa pe ecran numărul S, reprezentând suma maximă determinată.

Rezolvare

def maxima_suma(n, sir, k):

    sir.sort()  # Sortăm șirul pentru a identifica cele mai mici numere negative

    suma = 0

    count = 0

    for i in range(n):

        if sir[i] < 0 and count < k:  # Schimbăm semnul numai pentru elementele negative și doar de k ori

            sir[i] *= -1

            count += 1

    return sum(sir)  # Returnăm suma finală a întregului șir modificat

def main():

    n = int(input("Introduceți numărul de elemente din șir: "))

    sir = list(map(int, input("Introduceți elementele șirului separate prin spațiu: ").split()))

    k = int(input("Introduceți valoarea lui k: "))

    if k <= n:

        rezultat = maxima_suma(n, sir, k)

        print("Suma maximă obținută schimbând semnul a", k, "elemente distincte:", rezultat)

    else:

        print("k trebuie să fie mai mic sau egal cu n!")

if __name__ == "__main__":

    main()