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