Submatrix cu suma maxima

• Acest algoritm se bazează pe algoritmul lui Kadane
• Complexitate : O(N² * M)
•Pentru mai multe detalii : link

•Cod C++ : int kadane(int vec[], int s){ int sum = -1, maxi = INT_MIN; for(int i = 1; i <= s; i++){ if(sum < 0) sum = 0; sum += vec[i]; if(sum > maxi) maxi = sum; } return maxi; }

for(int i = 1; i <= n; i++){ for(int f = 1; f <= m; f++) s[f] = 0; for(int j = i; j <= m; j++){ for(int k = 1; k <= m; k++){ s[k] += a[j][k]; } sum = kadane(s, m); if(sum > maxi) maxi = sum; } }