3410 - Submatrix Sum Max - Revision history

Hotico Iulia Denisa: /* Cerință */

2023-11-13T19:11:04Z

Cerință

← Older revision		Revision as of 19:11, 13 November 2023
Line 2:		Line 2:

	==Cerință==		==Cerință==
			Se dă o matrice de numere întregi cu '''n''' linii și '''n''' coloane.
	Să se determine suma maximă care se poate obține dintr-o submatrice.		Să se determine suma maximă care se poate obține dintr-o submatrice.

Bonte Lucas Gabriel at 17:33, 13 November 2023

2023-11-13T17:33:06Z

← Older revision		Revision as of 17:33, 13 November 2023
Line 40:		Line 40:
	;Intrare		;Intrare

	:~~313~~		:1x

	;Ieșire		;Ieșire

Hotico Iulia Denisa: /* Exemplul 2 */

2023-11-13T13:10:05Z

Exemplul 2

← Older revision		Revision as of 13:10, 13 November 2023
Line 40:		Line 40:
	;Intrare		;Intrare

	:~~sdfhgdhfdtgh~~		:313

	;Ieșire		;Ieșire

Bonte Lucas Gabriel at 16:21, 11 November 2023

2023-11-11T16:21:16Z

← Older revision		Revision as of 16:21, 11 November 2023
Line 50:		Line 50:
	<syntaxhighlight lang="python" line="1" start="1">		<syntaxhighlight lang="python" line="1" start="1">

	def verificare_restrictii(numar): # functia de verificare a datelor de intrare		def verificare_restrictii(numar, matrix): # functia de verificare a datelor de intrare
	if 2 <= numar <= 20:		if 1 <= numar <= 300 and all(-1000 <= element <= 1000 for rand in matrix for element in rand):
	return True		return True
	else:		else:
Line 84:		Line 84:
	matrice = [list(map(int, input().split())) for _ in range(n)] # citirea matricei		matrice = [list(map(int, input().split())) for _ in range(n)] # citirea matricei

	if verificare_restrictii(n): # verificam datele de intrare		if verificare_restrictii(n, matrice): # verificam datele de intrare
	print("Datele de intrare corespund restrictiilor impuse.")		print("Datele de intrare corespund restrictiilor impuse.")
	print(suma_maxima_submatrice(n, matrice)) # apelam functia de rezolvare		print(suma_maxima_submatrice(n, matrice)) # apelam functia de rezolvare

Bonte Lucas Gabriel at 19:23, 10 November 2023

2023-11-10T19:23:30Z

← Older revision		Revision as of 19:23, 10 November 2023
Line 19:		Line 19:
	* O submatrice poate fi formată dintr-un singur element		* O submatrice poate fi formată dintr-un singur element

	==~~Exemplu~~==		==Exemplul 1==

	;Intrare		;Intrare
Line 31:		Line 31:

	;Ieșire		;Ieșire

			:Datele introduse corespund restricțiilor impuse.

	:18		:18

			==Exemplul 2==

			;Intrare

			:sdfhgdhfdtgh

			;Ieșire

			:Datele introduse nu corespund restricțiilor impuse.

	==Rezolvare==		==Rezolvare==
Line 38:		Line 50:
	<syntaxhighlight lang="python" line="1" start="1">		<syntaxhighlight lang="python" line="1" start="1">

	def ~~suma_maxima_submatrice~~(~~matrice~~):		def verificare_restrictii(numar): # functia de verificare a datelor de intrare
	n = ~~len~~(~~matrice~~) ~~# numărul de linii/coloane din matrice~~		if 2 <= numar <= 20:
			return True
			else:
			return False


			def suma_maxima_submatrice(numar, matrix):
	# inițializăm matricea de sume prefix cu 0		# inițializăm matricea de sume prefix cu 0
	prefix_sum = [[0 for _ in range(n + 1)] for _ in range(n + 1)]		prefix_sum = [[0 for _ in range(numar + 1)] for _ in range(numar + 1)]

	# calculăm matricea de sume prefix		# calculăm matricea de sume prefix
	for i in range(n):		for i in range(numar):
	for j in range(n):		for j in range(numar):
	prefix_sum[i + 1][j + 1] = ~~matrice~~[i][j] - prefix_sum[i][j] + prefix_sum[i][j + 1] + prefix_sum[i + 1][j]		prefix_sum[i + 1][j + 1] = matrix[i][j] - prefix_sum[i][j] + prefix_sum[i][j + 1] + prefix_sum[i + 1][j]

	max_sum = float('-inf') # inițializăm suma maximă cu -infinit		max_sum = float('-inf') # inițializăm suma maximă cu -infinit
	# parcurgem toate submatricile posibile		# parcurgem toate submatricile posibile
	for i in range(1, n + 1):		for i in range(1, numar + 1):
	for j in range(1, n + 1):		for j in range(1, numar + 1):
	for k in range(i, n + 1):		for k in range(i, numar + 1):
	for l in range(j, n + 1):		for lenght in range(j, numar + 1):
	# calculăm suma submatricei curente folosind sumele prefix		# calculăm suma submatricei curente folosind sumele prefix
	curr_sum = prefix_sum[k][l] - prefix_sum[k][j - 1] - prefix_sum[i - 1][l] + prefix_sum[i - 1][j - 1]		curr_sum = prefix_sum[k][lenght] - prefix_sum[k][j - 1] - prefix_sum[i - 1][lenght] + prefix_sum[i - 1][j - 1]
	max_sum = max(max_sum, curr_sum) # actualizăm suma maximă dacă este cazul		max_sum = max(max_sum, curr_sum) # actualizăm suma maximă dacă este cazul

	return max_sum # returnăm suma maximă		return max_sum # returnăm suma maximă

	~~# citim datele de intrare~~
	~~n = int(input())~~
	~~matrice = [list(map(int, input().split())) for _ in range(n)]~~
	~~# afișăm suma maximă a unei submatrici~~
	~~print(suma_maxima_submatrice(matrice))~~

			if __name__ == '__main__':
			try:
			n = int(input("Introduceti numarul de linii/coloane: ")) # citirea numarului de linii si coloane
			matrice = [list(map(int, input().split())) for _ in range(n)] # citirea matricei

			if verificare_restrictii(n): # verificam datele de intrare
			print("Datele de intrare corespund restrictiilor impuse.")
			print(suma_maxima_submatrice(n, matrice)) # apelam functia de rezolvare
			else:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			# ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
			except ValueError:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			except IndexError:
			print("Datele de intrare nu corespund restrictiilor impuse.")

	</syntaxhighlight>		</syntaxhighlight>

	==~~Explicatie~~==		==Explicație==
	; Submatricea de sumă maximă este:
	: '''2 4 5'''		Submatricea de sumă maximă este:
	: '''3 -2 6'''		:'''2 4 5'''
			:'''3 -2 6'''

Ghisa Catalin: /* Rezolvare */

2023-10-24T18:08:59Z

Rezolvare

← Older revision		Revision as of 18:08, 24 October 2023
Line 68:		Line 68:

	</syntaxhighlight>		</syntaxhighlight>

			==Explicatie==
			; Submatricea de sumă maximă este:
			: '''2 4 5'''
			: '''3 -2 6'''

Ghisa Catalin at 18:05, 24 October 2023

2023-10-24T18:05:28Z

← Older revision		Revision as of 18:05, 24 October 2023
Line 68:		Line 68:

	</syntaxhighlight>		</syntaxhighlight>

	~~==Explicație==~~

	~~Submatricea de sumă maximă este:~~
	~~:'''2 4 5'''~~
	~~:'''3 -2 6'''~~

Bonte Lucas Gabriel: Pagină nouă: Se dă o matrice de numere întregi cu '''n''' linii și '''n''' coloane. ==Cerință== Să se determine suma maximă care se poate obține dintr-o submatrice. ==Date de intrare== Programul citește de la tastatură numărul '''n''', iar apoi elementele matricei cu '''n''' linii și '''n''' coloane. ==Date de ieșire== Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice. ==Restricții de precizări== * 1 ⩽ n ⩽ 300 * Elementele ma...

2023-10-24T17:40:34Z

Pagină nouă: Se dă o matrice de numere întregi cu '''n''' linii și '''n''' coloane. ==Cerință== Să se determine suma maximă care se poate obține dintr-o submatrice. ==Date de intrare== Programul citește de la tastatură numărul '''n''', iar apoi elementele matricei cu '''n''' linii și '''n''' coloane. ==Date de ieșire== Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice. ==Restricții de precizări== * 1 ⩽ n ⩽ 300 * Elementele ma...

New page

Se dă o matrice de numere întregi cu '''n''' linii și '''n''' coloane.

==Cerință==

Să se determine suma maximă care se poate obține dintr-o submatrice.

==Date de intrare==

Programul citește de la tastatură numărul '''n''', iar apoi elementele matricei cu '''n''' linii și '''n''' coloane.

==Date de ieșire==

Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice.

==Restricții de precizări==

* 1 &les; n &les; 300
* Elementele matricei sunt numere întregi din intervalul '''[-1000, 1000]'''
* O submatrice poate fi formată dintr-un singur element

==Exemplu==

;Intrare

:5
:2 4 -1 2 -1
:4 -7 1 -6 -1
:-9 2 4 5 -7
:1 3 -2 6 2
:1 -4 -6 -5 8

;Ieșire

:18

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def suma_maxima_submatrice(matrice):
n = len(matrice) # numărul de linii/coloane din matrice
# inițializăm matricea de sume prefix cu 0
prefix_sum = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

# calculăm matricea de sume prefix
for i in range(n):
for j in range(n):
prefix_sum[i + 1][j + 1] = matrice[i][j] - prefix_sum[i][j] + prefix_sum[i][j + 1] + prefix_sum[i + 1][j]

max_sum = float('-inf') # inițializăm suma maximă cu -infinit
# parcurgem toate submatricile posibile
for i in range(1, n + 1):
for j in range(1, n + 1):
for k in range(i, n + 1):
for l in range(j, n + 1):
# calculăm suma submatricei curente folosind sumele prefix
curr_sum = prefix_sum[k][l] - prefix_sum[k][j - 1] - prefix_sum[i - 1][l] + prefix_sum[i - 1][j - 1]
max_sum = max(max_sum, curr_sum) # actualizăm suma maximă dacă este cazul

return max_sum # returnăm suma maximă

# citim datele de intrare
n = int(input())
matrice = [list(map(int, input().split())) for _ in range(n)]
# afișăm suma maximă a unei submatrici
print(suma_maxima_submatrice(matrice))

</syntaxhighlight>

==Explicație==

Submatricea de sumă maximă este:
:'''2 4 5'''
:'''3 -2 6'''