Using Max Sum Rectangle concept


#1

int kadane(int a[],int n)
{
int sum=0;
int maxsum=INT_MIN;
for(int i=0;i<n;i++)
{
sum+=a[i];
if(sum<0)
{
sum=0;
}
maxsum=max(maxsum,sum);

}
return maxsum;

}
int Solution::maximalRectangle(vector<vector > &A) {
int left,right;
int maxsum=INT_MIN;
int row=A.size();
int col=A[0].size();
int sum;
for(left=0;left<col;left++)
{
int temp[row]={0};
for(right=left;right<col;right++)
{
for(int i=0;i<row;i++)
{if(A[i][right]==0)/// if a submatrix contains 0, will put INT_MIN in temp array ,so that this 0 never contributes to the maximum sum subarray
{if(temp[i]>INT_MIN)/// if temp contains 0, we will put INT_MIN
{
temp[i]=INT_MIN;
}
else
{ /// else if temp[i] already contains INT_MIN, we will continue
continue;
}
}
else
{temp[i]+=A[i][right];} /// if the number is 1, we will simply add
}

    sum=kadane(temp,row);
    if(sum>maxsum)
    {
        maxsum=sum;
    }
    }
}
return maxsum;

}