CareerCup

I'm not sure if this algorithm is fast enough
- Solve the problem for the case m = 1 first
- Then solve the problem for the case n = 1
- Use your subroutines to construct a matrix whose each entry (i,j) is the sum of the kxk matrix starting at index (i,j) of the original matrix

Algo.
Using tabulation :
Keep another matrix Mat[][] with dimension nXm with each element saving both size of max sq matrix till now and its sum.
At any pt. while filling the matrix element (i, j) we have 2 options.. either choose (i-1,j-1) and add to it (i-1, j), (i, j-1) and (i, j) or just choose element (i,j). Out choice will depend on the condition max(sum(i-1,j-1)+A[i-1][j]+A[i][j-1]+A[i][j], A[i][j]) where A is the matrix given.

Code in java:

class Element {
 int size;
 int sum;
}

void printMaxSubmatrix(int[][] A) {
 int n = A.length;
 int m = A[0].length;
 Element[][] Mat = new Element[n][m];
 for(int i = 0; i < n; ++i)
  for(int j = 0; j < m; ++j) 
   Mat[i][j] = new Element();

 int max = -1;
 int row = -1;
 int col = -1;
 for(int i = 0; i < n; ++i) {
  Mat[i][0].size = 1;
  Mat[i][0].sum = A[i][0];
  if(Mat[i][0].sum > max) {
   max = Mat[i][0].sum;
   row = i;
   col = 0;
  }
 }
 for(int i= 0; i <m ; ++i) {
  Mat[0][i].size = 1;
  Mat[0][i] = A[0][i];
  if(Mat[0][i].sum > max) {
   max = Mat[0][i].sum;
   row = 0;
   col = i;
  }
 }

 for(int i = 1; i < n; ++i) {
  for(int j = 1; j < m; ++j) {
   int sum = A[i][j];
   int size = 1;
   if(sum <= Mat[i-1][j-1].sum+A[i-1][j]+A[i][j-1]+A[i][j]) {
    sum = Mat[i-1][j-1].sum+A[i-1][j]+A[i][j-1]+A[i][j];
    size = Mat[i-1][j-1].size+1;
  }
  Mat[i][j].sum = sum;
  Mat[i][j].size = size;
  if(sum > max) {
   max = Mat[i][j];
   row = i;
   col = j;
  }
 }
 
 for(int i = row-Mat[row][col].size+1; i <= row; ++i) {
  for(int j = col-Mat[row][col].size+1; j <= col; ==j) {
   System.out.print(A[i][j]);
 }
System.out.println();
}   
}

Find sum of elements from A[i][j] position to A[i][j+k] as sum[i][j];
sum(0,0) = A[0][0] to A[0][k-1];
sum(i,j) = sum(i,j-1)-A[i][j] + A[i][j+k]; 0>= i > m && 0>= j > n-k-1
Find sum of elements of submatrix of size k.
ksum(i,j) represents sum of submatrix of from A[i][j] to k x k subarray.
ksum(i,j) = ksum(i-1,j) - sum(i,j) + sum(i+k,j);

only corner case I might have missed .like k-1 or k+1 ..

This seems a little weird question :) , assume all the elements are non-negative integers. Then the largest sum should include as many elements as possible. Therefore the length of the edges of the matrix should be (m-1)x(n-1), this implies that there are only 5 matrices possible :) . why DP ?

What the hell is a freakin DP that you people keep talking about?

If avoiding redundant additions is the requirement , following solution can be useful:

Create matrix2[m][n/2] matrix such that, addition of two consecutive numbers in matrix[m][n] is put in matrix2[][].
For example if matrix[0] looks like {0,1,2,3}
then matrix2[0] will be {1,5} // 0+1 =1 , 2+3=5

Again create a matrix using matrix2[][] using same logic.

By using this calculating sum of matrix[k][k] can be efficient.

#include<bits/stdc++.h>
using namespace std;
int maxsum(int a[][5],int k)
{
int s[5][5-k+1];
for(int i = 0;i<5;i++){
s[i][0] = 0;
for(int j = 0;j<k;j++)
s[i][0]+= a[i][j];
}
for(int i = 0;i<5;i++){
for(int j = 1;j<5-k+1;j++){
s[i][j] = s[i][j-1]-a[i][j-1]+a[i][j+k-1];
}
}

int s2[5-k+1][5-k+1]; int ma = INT_MIN;

for(int j = 0;j<5-k+1;j++){
s2[0][j] = 0;
for(int l = 0;l<k;l++)
s2[0][j]+= s[l][j];
ma = max(ma,s2[0][j]);
}

for(int i = 1;i<5-k+1;i++)
for(int j = 0;j<5-k+1;j++)
{
s2[i][j] = s2[i-1][j]-s[i-1][j]+s[i+k-1][j];
ma = max(ma,s2[i][j]);
}
return ma;

}int main()
{
int a[5][5] = {{1,4,2,3,2},{1,6,3,9,2},{1,3,2,5,6},{9,7,8,5,4},{4,6,2,9,1}}
;
cout<<maxsum(a,3); //k = 3,m = 5,n = 5;
}

{#include<bits/stdc++.h>
using namespace std;
int maxsum(int a[][5],int k)
{
int s[5][5-k+1];
for(int i = 0;i<5;i++){
s[i][0] = 0;
for(int j = 0;j<k;j++)
s[i][0]+= a[i][j];
}
for(int i = 0;i<5;i++){
for(int j = 1;j<5-k+1;j++){
s[i][j] = s[i][j-1]-a[i][j-1]+a[i][j+k-1];
}
}

int s2[5-k+1][5-k+1]; int ma = INT_MIN;

for(int j = 0;j<5-k+1;j++){
s2[0][j] = 0;
for(int l = 0;l<k;l++)
s2[0][j]+= s[l][j];
ma = max(ma,s2[0][j]);
}

for(int i = 1;i<5-k+1;i++)
for(int j = 0;j<5-k+1;j++)
{
s2[i][j] = s2[i-1][j]-s[i-1][j]+s[i+k-1][j];
ma = max(ma,s2[i][j]);
}
return ma;

}int main()
{
int a[5][5] = {{1,4,2,3,2},{1,6,3,9,2},{1,3,2,5,6},{9,7,8,5,4},{4,6,2,9,1}}
;
cout<<maxsum(a,3); //k = 3,m = 5,n = 5;
}
}

#include<bits/stdc++.h>
using namespace std;
int maxsum(int a[][5],int k)
 {
    int s[5][5-k+1];
    for(int i = 0;i<5;i++){
        s[i][0] = 0;
    for(int j = 0;j<k;j++)
    s[i][0]+=  a[i][j];
    }
    for(int i = 0;i<5;i++){
    for(int j = 1;j<5-k+1;j++){
    s[i][j] = s[i][j-1]-a[i][j-1]+a[i][j+k-1];
}
    }

    int s2[5-k+1][5-k+1]; int ma = INT_MIN;

    for(int j = 0;j<5-k+1;j++){
    s2[0][j] = 0;
    for(int l = 0;l<k;l++)
    s2[0][j]+= s[l][j];
    ma = max(ma,s2[0][j]);
    }

    for(int i = 1;i<5-k+1;i++)
    for(int j = 0;j<5-k+1;j++)
    {
        s2[i][j] = s2[i-1][j]-s[i-1][j]+s[i+k-1][j];
        ma = max(ma,s2[i][j]);
    }
    return ma;

}int main()
{
    int a[5][5] = {{1,4,2,3,2},{1,6,3,9,2},{1,3,2,5,6},{9,7,8,5,4},{4,6,2,9,1}}
;
cout<<maxsum(a,3); //k = 3,m = 5,n = 5;
}

;k;x

If k is already given, then I think its pretty straighforward. Perhaps I am overlooking something but there does not seem to be any scope for DP.
Just check for each element, the kxk matrix starting from there and keep updating max.. O(mn)