Maximum Sub Square Matrix Sum Less Than K

There is a matrix of size nxn and we are given a threshold value k. We need to make a function which returns the highest sub square matrix we can find which has a total sum less than k and the sub square matrix should be able to occupy the complete matrix at every possible position. For example, imagine we have a matrix of size 3x3 1 1 1 1 1 1 1 1 1 Where k is 4. We would like to return the length of the valid sub square matrix which sums up to less than k. So in this case, the way we would compute the result is first by taking sub matrices of size 1x1. [1] [1] [1] [1] [1] [1] [1] [1] [1] Since the sum of each of the submatrices does not exceed k, the current result stands at 1. Now let's try for 2x2. [1 1] 1 1 [1 1] 1 1 1 1 1 1 [1 1] 1 1 [1 1] [1 1] 1 1 [1 1] 1 1 1 & 1 1 1 & [1 1] 1 & 1 [1 1] Now as you can see that the sum of each of the sub matrices is 4 which stays inside the threshold, the result is now 2. Now let's finally try for 3x3. [1 1 1] [1 1 1] [1 1 1] The sum exceeds the threshold since it is 9. Hence, we would result 2 as the answer since the maximum sub square matrix we could make which stayed inside the threshold was of size 2.