Prelucrarea optimă a submatricilor
1. Submatrice de sumă maximă1
Se dă o matrice de dimensiuni N x N cu elemente întregi. Se cere determinarea unei submatrici a
cărei elemente au suma maximă.
Exemplu: pentru n = 4 și matricea se va afișa 15, submatricea de suma
maximă fiind: .
Rezolvare:
- Cu două variabile left și right vom fixa coloana din stânga respectiv coloana din dreapta a
unei submatrici.
- vom calcula suma elementelor de pe fiecare linie situată între coloanele left și right. Vom
avea n astfel de sume pe care le reținem într-un vector.
- Vom determina subsecvența de sumă maximă pentru vectorul astfel format.
- Rezultatul va fi valoarea maximă dintre subsecvențele de sumă maximă.
Pentru left=1 și right =1, formăm vectorul alăturat și vom obține subsecvența de sumă
maximă 9.
Pentru left=1 și right =2, formăm vectorul alăturat și vom obține subsecvența de sumă
maximă 15.
1
UVA 108 - Maximum Sum
[Link]
oblem=44
Subalgoritm submatriceSumaMax (intreg a[][], intreg nrLin, intreg nrCol)
maxSum 0 //daca matricea are numai valori negative alta valoare
pentru left 1, nrCol executa // fixam stanga
pentru i nrLin executa
v[i] 0 //initializam elementele vectorului
sf. pentru
pentru right left, nrCol executa //fixam marginea dreapta
v[i] v[i] + a[i][right] //calculam sumele aferente
sum subsecventaSumMax(v,nrLin)
//retinem subsecventa de suma max
daca maxSum < sum atunci
maxSum sum
sf. daca
sf. pentru
sf. pentru
return maxSum //sau scrie maxSum
sf. subalgoritm
Complexitate O(n3).
2. Submatrice maximală de dimensiune k x k
Se dă o matrice de dimensiune n x n. Să se determine sumele elementelor tuturor submatricilor
de dimensiune k x k (k ≤ n).
n = 3, k = 2
m[][] = { {1, 2, 3},
{4, 5, 6},
{7, 8, 9},
};
Output:
12 16
24 28
Există o soluție de complexitate O(n2).
- Se rețin într- matrice auxiliară sumele tuturor benzilor vertical de dimensiune k x 1 (k
linii și o coloana)
o Pentru exemplul de mai sus vom avea {5, 7, 9}
{11, 13, 15}
- Pe fiecare linie se calculează sum a k elemente consecutive
//formam matricea auxiliara formata din benzi de dimensiune kX1
pentru j 1, n executa // parcurgem matricea pe coloane
sum 0 //initial pentru fiecare banda
//calculam suma primelor k elemente de pe coloana j
pentru i 1, k executa
sum sum + a[i][j]
sf. pentru
aux[1][j] sum //primul element de pe coloane retine suma primilor k
pentru i k+1, n executa //pentru celelalte elemente
sum = sum + (a[i][j]-a[i-k][j]) //adunam urm element si scadem primul
aux[i-k+1][j] sum
sf. pentru
sf. pentru
//adunam k elemente consecutive pe fiecare linie
pentru i 1, k executa
sum 0
pentru j 1, k executa //calcukam suma primilor k termini
sum sum + aux[i][j]
sf. pentru
Following is C++ implementation of this idea.
scrie sum, “ ”
pentru j k+1, n-k+2 executa
sum sum + aux[i][j] – aux[i][j-k]
scrie sum, “ ”
sf. pentru
scrie salt_la_rand_nou
sf. pentru