Maximum Sub-square Sum in O(N2)

Revision en1, by jha_gaurav98, 2018-06-30 15:38:23

Given a square array of size N × N where each cell is filled with a number between  - 9 and 9. A sub square of size k is any set of k contiguous columns and k contiguous rows. For any sub square, the sum of elements in its cells is called a sub square sum. Given the N × N square, write a program to find the maximum sub square sum. (Note that a 1 × 1 square (k = 1) is not considered a sub square)

Constraints: 2 ≤ N ≤ 1000

By looking at the constraints I think we have to do it in O(N2). I could manage to reach to O(N3). Please Help

Thanks in advance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English jha_gaurav98 2018-06-30 15:38:55 3
en1 English jha_gaurav98 2018-06-30 15:38:23 642 Initial revision (published)