Maximum number of 1’s in a submatrix of given area in a binary matrix

Firstly, let me make the statement clear. You will be given a binary matrix. A binary matrix is one which only consists of 1’s and 0’s. You will be asked to find a maximum number of 1’s in rectangular sub-matrix of a given area.

Naive Approach:
Find all possible rectangles for given area.
For all possible rectangles in given matrix, find number of 1’s in given area.

(I will be discussing for a square matrix of dimensions NxN. Similar solution for any rectangular matrix can be constructed)

for(i = 1;i <= N;i++)
{
	if(area%i == 0 && area/i <= N) 
	{//(area/i) should be less than N else the rectangle goes is out of NxN
		x = i;
		y = area/i;
		for(j = 1;j <= N;j++)
		{
			for(k = 1;k <= N;k++)
			{
				if(j+x-1 <= N && k+y-1 <= N)
				{//checking if other ends lie in range of matrix dimensions
					temp = 0;
					for(l = j; l <= j+x-1 ; l++)
					{//here I find number of 1's in the rectangle
						for(m = k;m <= k+y-1; m++)
						{
							if(a[l][m] == 1)
								temp++;
						}
					}
					if(temp > max)
						max = temp;
				}
				if(j+y-1 <= N && k+x-1 <= N)
				{//this is another rectangle of same dimensions but different orientation
					temp = 0;
					for(l = j; l <= j+y-1 ; l++)
					{
						for(m = k;m <= k+x-1; m++)
						{
							if(a[l][m] == 1)
								temp++;
						}
					}
					if(temp > max)
						max = temp;
				}
			}
		}
	}
}
printf("%d\n",max);

This approach takes a long time to give output for even a values of N around 100. Let us now learn a better approach to this problem.

Solving using Dynamic programming :
We can construct a 2d DP where dp[x][y] has number of 1’s in submatrix a[i][j] where 1 ≤ i ≤ x and 1 ≤ j ≤ y.
The DP can be constructed by this formula

dp[i][j] = 	dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]	    ,if a[i][j] = 0
		dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + 1  ,if a[i][j] = 1

In single statement,

dp[i][j] =     dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j]

Understanding the formula : For dp[x][y], we add (number of 1’s in sub-matrix a[i][j], where 1 ≤ i ≤ x and 1 ≤ j ≤ y-1) and (number of 1’s in sub-matrix a[i][j], where 1 ≤ i ≤ x-1 and 1 ≤ j ≤ y).
In doing this we add a sub-matrix a[i][j], where 1 ≤ i ≤ x-1 and 1 ≤ j ≤ y-1 twice. So we subtract that value from the sum.
And lastly, we check if the value at a[i][j] is 1 or not and add the value to sum.

Now we find all possible dimensions of the rectangles, and find number of 1’s in all these rectangles. Return maximum of values found as answer.

How to find number of 1’s in a rectangle now? For example, you are at index (x,y) and dimensions of rectangle is (r,s), number of 1’s in that rectangle would be,

dp[x+r-1][y+s-1] - (dp[x+r-1][y-1] + dp[x-1][y+s-1]) + dp[x-1][y-1].

This is much similar as the way in DP formula that we discussed earlier.

void constructDP(int a[][1001],int dp[][1001])
{
	for (int i = 0; i <= n; ++i)
	{
		dp[0][i] = 0;
		dp[i][0] = 0;
	}
	for (int i = 1; i <= n; ++i)
	{
		for(int j = 1;j <= n; ++j)
		{
			dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j];
		}
	}
}

int solve(int a[][1001],int dp[][1001],int n)
{
	constructDP(a,dp);
	ans = INT_MAX;
	for (int i = 1; i <= n; ++i)
	{
		if(count%i == 0 && count/i <= n)
		{
			x = i;
			y = count/i;
			for(int j = 1;j <= n;j++)
			{
				for(int k =1; k <= n;k++)
				{
					if((j+x-1 <= n) && (k+y-1 <= n))
						ans = max(ans, dp[j+x-1][k+y-1]-dp[j-1][k+y-1]-dp[j+x-1][k-1]+dp[j-1][k-1]);
					if((j+y-1 <= n) && (k+x-1 <= n))
						ans = max(ans, dp[j+y-1][k+x-1]-dp[j-1][k+x-1]-dp[j+y-1][k-1]+dp[j-1][k-1]);
				}
			}
		}
	}
	return ans;
}

Using the function, you can note that, with a O(N2) pre-computation, we reduce a query of finding number of 1’s in a rectangle every time from O(N2) to O(1).

Problems related with this concept : SWAPMATR

Maximum Subarray Sum algorithm

This algorithm is used to find the maximum sum of a contiguous sub array in a given array of integers. If the set of integers include only positive integers, maximum sum would be sum of all the elements of array. But when the array include negative integers too, the problem comes of how to solve it efficiently.

A naive approach would be finding sum of elements of all sub arrays.

MaxSubarraySumNaive(a[])
    max = 0
    for i = 1 to n
        for j = i to n
            temp = 0
            for k = i to j
                temp = temp + a[i]
            if temp > max
                max = temp
    return max

That’s an O(n3) solution which is not at all appreciable. So let’s learn this algo which could solve this problem with an O(n) complexity.

MaxSubarraySum(a[])
    max_sum = 0
    temp = 0
    for i = 1 to n
        temp = max( 0 , temp+a[i] )
        max_sum = max( max_sum , temp )
    return max_sum

This short function solves the problem in real quick time. Working of the function with an example is shown below

For increasing i,
Array elements  : 1 -2 8 -1  6  3 -12  4 -16  5 10
temp values     : 1  0 8  7 13 16   4  8   0  5 15
max_sum values  : 1  1 8  8 13 16  16 16  16 16 16