Given a square array of size $N \times 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 \times N$ square, write a program to find the maximum sub square sum. ↵
(Note that a $1 \times 1$ square $(k=1)$ is not considered a sub square)↵
↵
Constraints: $ 2 \leq N \leq 1000 $↵
↵
By looking at the constraints I think we have to do it in $O(N^2)$. I could manage to reach to $O(N^3)$. ↵
Please Help↵
↵
Thanks in advance
(Note that a $1 \times 1$ square $(k=1)$ is not considered a sub square)↵
↵
Constraints: $ 2 \leq N \leq 1000 $↵
↵
By looking at the constraints I think we have to do it in $O(N^2)$. I could manage to reach to $O(N^3)$. ↵
Please Help↵
↵
Thanks in advance