#codingexercise
Find the largest rectangular sub-matrix having sum divisible by k.
The naive approach is to exhaust all the rectangular sub matrices to find the sums. check that the sums are divisible by k and then update the max of the rectangular size found so far.
This appears something like
int GetLargest(int[,] M, int R, int C, int k)
{
int max = 0;
// Every element forms the top left corner of a rectangular area of different sizes
for (int i = 0; i < R; i++)
  for (int j = 0; j < C; j++)
{
   int kx = i;
   int ky = j;

    for (int m = kx; m < R; m++)
         for (int n = ky; n < C; n++)
    {
           int sum = GetSum(M, i,j,m,n);
           if (sum % k == 0)
           {
                    int size = GetSize(i,j,m,n);
                    if (size > max)
                        max = size;
           }
    }
return max;
}
The above is O(N^3) complexity as the 2D iterations are performed for every coordinate in the rectangular area
As we can see that this has a lot of overlapping regions that are summed again and again.
Instead, we could enumerate all the possible rectangular areas to be bounded in the matrix between a pair of left and right columns and a pair of top and bottom rows with the temporary sums along each row and column The temporary sums are in a linear array and we can now use the algorithm to find the longest sub-array having sum divisible by k to find the rectangular sub area in this 2D scan.