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(N²). I could manage to reach to O(N³). Please Help

Thanks in advance