3937 - KSum3: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 10: Line 10:


== Date de ieșire ==  
== Date de ieșire ==  
Programul va afișa pe ecran numărul S, reprezentând suma maxima a unei subsecvențe care respectă condițiile din enunț.
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 ==
== Restricţii şi precizări ==
Line 20: Line 21:
: 5 4 -10 1 2 3
: 5 4 -10 1 2 3
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct.
: 6
: 6


Line 31: Line 34:
     array = list(map(int, input().split()))
     array = list(map(int, input().split()))
     return n, k, w, array
     return n, k, w, array


def maximum_subarray_sum(n, k, w, array):
def maximum_subarray_sum(n, k, w, array):
Line 45: Line 49:
                 dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])
                 dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])
     return max(dp[k - 1:n])
     return max(dp[k - 1:n])


def validate_input(n, k, w, array):
def validate_input(n, k, w, array):
Line 53: Line 58:
             return False
             return False
     return True
     return True


if __name__ == '__main__':
if __name__ == '__main__':
     n, k, w, array = read_input()
     n, k, w, array = read_input()
     if validate_input(n, k, w, array):
     if validate_input(n, k, w, array):
         print(maximum_subarray_sum(n, k, w, array))
         result = maximum_subarray_sum(n, k, w, array)
        print("Datele sunt introduse corect.")
        print(result)
     else:
     else:
         print("Input is not valid!")
         print("Datele nu corespund restricțiilor impuse.")





Revision as of 14:44, 28 April 2023

Sursa: 3937 - KSum3


Cerinţa

Se dă N și un vector de N elemente numere întregi, găsiți suma maximă a unei subsecvențe (elemente adiacente) cu lungimile cuprinse între K și W (K <= lungime <= W).


Date de intrare

Programul citește de la tastatură numerele N, K, W iar apoi un vector de N numere întregi.


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

  • 1 ≤ K ≤ W ≤ N ≤ 1.000.000
  • cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000].crescător

Exemplu

Intrare
6 3 4
5 4 -10 1 2 3
Ieșire
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct.
6

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 3937 - KSum3

def read_input():

   n, k, w = map(int, input().split())
   array = list(map(int, input().split()))
   return n, k, w, array


def maximum_subarray_sum(n, k, w, array):

   dp = [0] * (n + 1)
   prefix_sum = [0] * (n + 1)
   prefix_sum[0] = array[0]
   for i in range(1, n):
       prefix_sum[i] = prefix_sum[i - 1] + array[i]
   for length in range(k, w + 1):
       for i in range(length - 1, n):
           if i == length - 1:
               dp[i] = prefix_sum[i]
           else:
               dp[i] = max(dp[i - 1] + array[i], prefix_sum[i] - prefix_sum[i - length])
   return max(dp[k - 1:n])


def validate_input(n, k, w, array):

   if not (1 <= k <= w <= n <= 1000000):
       return False
   for num in array:
       if not (-1000000000 <= num <= 1000000000):
           return False
   return True


if __name__ == '__main__':

   n, k, w, array = read_input()
   if validate_input(n, k, w, array):
       result = maximum_subarray_sum(n, k, w, array)
       print("Datele sunt introduse corect.")
       print(result)
   else:
       print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input() citește de la tastatură numerele N, K, W și un vector de N numere întregi și le returnează. Funcția maximum_subarray_sum() primește N, K, W și vectorul citit de la tastatură și returnează suma maximă a unei subsecvențe cu lungimile cuprinse între K și W. Algoritmul folosește programarea dinamică și calculează suma maximă a unei subsecvențe pentru fiecare lungime între K și W. Pe baza acestor calcule se determină suma maximă a întregului vector. Funcția validate_input() primește N, K, W și vectorul citit de la tastatură și verifică dacă acestea respectă condițiile problemei. În funcția principală se citesc datele de intrare, se validează și se apelează funcția de calcul a sumei maxime a unei subsecvențe.