Algoritmul lui Kadane: subtabloul cu suma maxima. Implementarea in tablouri unidimensionale si bidimensionale

Atunci cand avem un vector doar cu elemente pozitive (spre exemplu V⁴={1,3,11,4}) problema determinarii subarray-ul cu suma maxima este elementara, subarray-ul cautat fiind array-ul in sine. Problema devine mult mai interesanta atunci cand se adauga si numere negative. In mod intuitiv se foloseste o structura de tip “for in for” care calculeaza suma tuturor subarray-urilor si determina maximul.
Mai jos se poate vedea algoritmul naiv, ce foloseste aceasta abordare. Complexitatea este una patratica O(n²), lucru ce nu este ideal pentru anumite probleme de concurs unde se dau vectori cu un numar mare de elemente.
#include <iostream> #include <climits> using namespace std; int main() { int n,v[100],s,maxim; cin>>n; for(int i=0;i<n;i++) { cin>>v[i]; } maxim=v[0]; for(int i=0;i<n;i++) { s=0; for(int j=i;j<n;j++) { s=s+v[j]; } maxim=max(maxim,s); } cout<<maxim; return 0; }
Se propune o alta solutie mai eficienta: insumam elementele vectorului pana cand suma este mai mica ca elementul individual din vector. In acel moment suma incepe de la elementul gasit. De fiecare data se verifica daca suma curenta este mai mare ca maximul global. Aceasta maniera de rezolvare va avea timp de compilare O(n) ideal pentru concursuri.
#include <iostream> using namespace std; int main() { int n,v[100],maxim,curent; cin>>n; for(int i=0;i<n;i++) { cin>>v[i]; } maxim=v[0]; curent=v[0]; for(int i=1;i<n;i++) { curent=max(v[i],curent+v[i]); maxim=max(maxim,curent); } cout<<maxim; return 0; }
Folosindu-ne de acest algoritm putem determina si submatricea cu suma maxima, coreland sumele partiale pe linii sau coloane cu aceasta abordare. Complexitatea este O(n²•m). Mai jos este si codul:
#include <iostream> using namespace std; int main() { int n, m; int a[100][100]; cin >> n >> m; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> a[i][j]; } } int maxim = -1000000; for(int sus = 0; sus < n; sus++) { int v[100] = {0}; for(int jos = sus; jos < n; jos++) { for(int col = 0; col < m; col++) v[col] = v[col] + a[jos][col]; int curent = v[0]; int max_local = v[0]; for(int i = 1; i < m; i++) { curent = max(v[i], curent + v[i]); max_local = max(max_local, curent); } if(max_local > maxim) maxim = max_local; } } cout << maxim; return 0; }
Sper ca v-am ajutat!