This is a dynamic programming problem based on sliding window type of thing.In this problem We have to find the k*k size submatrix whoose sum is maximum.
here is the solution of the problem.
<br />#include<bits/stdc++.h>
using namespace std;
int main(){
int m,n,k;
cout<<"enter value of m , n, k"<<endl; cin>>m>>n>>k;
cout<<"enter matrix"<<endl;
int matrix[m][n];
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++) cin>>matrix[i][j];
int sum = 0;
int sum_matrix[m][n-k+1];
for(int i = 0 ; i < m; i++){
sum = 0;
for(int j = 0; j < k; j++)
sum = sum + matrix[i][j];
sum_matrix[i][0] = sum;
// cout<<sum<<" ";
}
// cout<<endl<<endl;;
for(int i = 0; i < m; i++){
for(int j = 1 ; j < n-k+1; j++){
sum_matrix[i][j] = sum_matrix[i][j-1] + matrix[i][j+k-1]- matrix[i][j-1];
// cout<<sum_matrix[i][j]<<" ";
}
// cout<<endl;
}
//cout<<endl;
int maxs = INT_MIN;
int ksum_matrix[m-k+1][n-k+1];
int ksum = 0;
for(int j = 0 ; j < n-k+1; j++){
ksum = 0;
for(int i = 0; i < k; i++) ksum = ksum + sum_matrix[i][j]; if(ksum > maxs)
maxs = ksum;
ksum_matrix[0][j] = ksum;
// cout<<ksum<<" ";
}
// cout<<endl<<endl;
int maxm = maxs;
for(int j = 0; j < n-k+1; j++){
for(int i = 1 ; i < m-k+1; i++){
ksum_matrix[i][j] = ksum_matrix[i-1][j] + sum_matrix[i+k-1][j]- sum_matrix[i-1][j];
// cout<<ksum_matrix[i][j]<<" ";
if(maxm < ksum_matrix[i][j])
maxm = ksum_matrix[i][j];
}
// cout<<endl;
}
cout<<"max sum = "<<maxm;
}
Output :-
Myprogworld 