c) Se dă o matrice și se cere determinarea unui dreptunghi de sumă maximă. Ultimul algoritm prezentat poate fi extins pentru rezolvarea problemei în O(N3). Cum?
Ultimul algoritmul prezentat în pagina de la linkul de mai sus este:
- maximul global este inițial primul număr.
- suma maximă ce se poate obține dintr-o subsecvență care se termină pe poziția primului element este primul element
- pentru fiecare element de la al doilea până la sfârșit
- suma maximă a unei subsecvențe ce se termină pe poziția curentă este fie valoarea elementului curent, fie suma obținută dintr-o subsecv. ce se termină pe poziția anterioară + valoarea elementului curent
- dacă suma maximă obținută pe poziția curentă este > decât maximul global, maximul global devine suma curentă
Problemă similară la sfârșitul capitolului:
- Scrieți un program care răspunde eficient la mai multe interogări privind suma unor dreptunghiuri ale unei matrice.
rezolvată ineficient aici. Deosebirea de această problemă pe care am rezolvat-o deja este că nu se cer sume de dreptunghiuri ci un dreptunghi de sumă maximă.
- nu trebuie să calculez toate sumele ci să calculez inteligent doar sumele necesare dreptunghiului de sumă maximă, dacă e posibil.
Articolul prezent este inspirat din acest articol.
Dată fiind o matrice, găsiți submatricea de sumă maximă din ea. De exemplu, în următoarea matrice, submatricea de sumă maximă este evidențiată cu dreptunghi albastru și suma acestei submatrice este 29.
Problema este mai ales o extensie a problemei subsecvenței de sumă maximă a unui vector.
Soluția naivă pentru această problemă este să se verifice fiecare dreptunghi posibil în matricea dată. Această soluție cere 4 cicluri îmbricate și complexitatea timp a acestei soluții ar fi O(N4). [ n.e. Aici am rezolvat naiv problema. ]
Algoritmul lui Kadane pentru un vector poate fi folosit pentru a reduce complexitatea timp la O(N3). Ideea este să se fixeze coloanele din stânga și din dreapta una câte una și să se găsească rândurile consecutive de sumă maximă pentru fiecare pereche de coloane, una din stânga și una din dreapta. Practic se găsesc numerele de rând de sus și de jos (care au suma maximă) pentru fiecare pereche fixată de coloane din stânga și dreapta. Pentru a găsi numerele de rânduri de sus și de jos, se calculează suma elementelor în fiecare rând de la stânga la dreapta și se stochează aceste sume într-un vector, de exemplu temp[]. Deci temp[i] indică suma elementelor de la stânga la dreapta în rândul i. Dacă se aplică algoritmul lui Kadane pe temp[], și găsim subvectorul de sumă maximă a lui temp, această suma maximă ar fi suma maximă posibilă cu stânga și dreapta ca fiind coloanele mărginitoare. Pentru a găsi suma maximă finală, comparăm această sumă cu suma maximă de până acum.
Metoda descrisă în articol funcționează pentru oricare numere reale.
Cod sursă
#include <fstream>
#include <vector>
using namespace std;
double subsecv_de_suma_maxima(vector<double> &A,
int &inceput, int &sfarsit)
{
int N = A.size() - 1;
double max = A[1];
int inceput_temp = 1;
vector<double> S(N + 1);
S[1] = A[1];
inceput = sfarsit = 1;
for (int i = 2; i <= N; ++i)
{
if (S[i - 1] + A[i] > A[i])
{
S[i] = S[i - 1] + A[i];
}
else
{
inceput_temp = i;
S[i] = A[i];
}
if (S[i] > max)
{
inceput = inceput_temp;
sfarsit = i;
max = S[i];
}
}
return max;
}
double suma_max_in_dreptunghi(vector<vector<double>> &D, int r, int c,
int &stanga, int &dreapta, int &sus, int &jos)
{
double suma_max = D[1][1];
for (int st = 1; st <= c; ++st)
{
vector<double> temp(r + 1, 0);
// cand dr == st, e o submatrice-coloana
for (int dr = st; dr <= c; ++dr)
{
// pt. fiecare rand se adauga elementul curent
// din el la elementul corespunzator din temp
for (int i = 1; i <= r; ++i)
{
temp[i] += D[i][dr];
}
int inceput, sfarsit;
double suma = subsecv_de_suma_maxima(temp, inceput, sfarsit);
if (suma > suma_max)
{
suma_max = suma;
stanga = st;
dreapta = dr;
sus = inceput;
jos = sfarsit;
}
}
}
return suma_max;
}
int main()
{
int r, c;
ifstream in("suma.in");
in >> r >> c;
vector<vector<double>> D(r + 1, vector<double>(c + 1));
for (int i = 1; i <= r; ++i)
{
for (int j = 1; j <= c; ++j)
{
in >> D[i][j];
}
}
in.close();
int stanga, dreapta, sus, jos;
double suma_maxima = suma_max_in_dreptunghi(
D, r, c, stanga, dreapta, sus, jos);
ofstream out("suma.out");
out << suma_maxima << endl;
out << "(" << sus << ", " << stanga << ")" << endl;
out << "(" << jos << ", " << dreapta << ")" << endl;
out.close();
return 0;
}
Intrare
3 4
0.5 0.1 0.8 -0.90.4 0.2 6 0.3
4 0.8 0.9 1
Ieșire
14.1
(1, 1)(3, 4)
Prezentare
Schemă
