Submatrix sum using prefix sum matrix

#1

#include
using namespace std;
int main() {
int a[100][100]={0},n,sum=0;
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
for(int i =0;i<n;i++)
{
for(int j=1;j<n;j++)
{
a[i][j]=a[i][j]+a[i][j-1];
}
}
for(int i =1;i<n;i++)
{
for(int j=0;j<n;j++)
{
a[i][j]=a[i][j]+a[i-1][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;i<n;j++)
{
for(int l=i;l<n;l++)
{
for(int k=j;k<n;k++)
{
if(i!=0 && j!=0)
{
sum+=a[l][k]-a[l][j-1]-a[i-1][k]+a[i-1][j-1];
}
else if(i==0 && j!=0)
{
sum+=a[l][k]-a[l][j-1];
}
else if(j==0 && i!=0){
sum+=a[l][k]-a[i-1][k];
}
else if(i==0 && j==0){
sum=sum+a[l][k];
}
}
}
}
}
cout<<sum;
}
//this is showing TLE whats the problem wth this code and there is a better way to solve the boundary condition

#2

Hi @Marr_iss,
in dis,
for(int i=0;i<n;i++)
{
for(int j=0;i<n;j++)
{
for(int l=i;l<n;l++)
{
for(int k=j;k<n;k++)
in ur second for loop, use j<n instead of i<n.
Moreover, u will see that ur a[][] is not getting generated correctly. Pls refer to lecture for its approach and code.
In order to optimize ur code(to n^2), u can refer to approach 3 lecture of the same problem.
If u still face any problem,feel free to ask and post it here.
Hope dis helps.

#3

thank you a silly mistake

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.