Wsrtjtyk

I want find the biggest submatrix which contains only negative numbers in a matrix, for example:

In

[[1,  -9, -2,   8,  6,  1],    

 [8,  -1,-11,  -7,  6,  4],    

 [10, 12, -1,  -9, -12, 14],    

 [8, 10, -3,  -5,  17,  8],    

 [6,  4, 10, -13, -16, 19]]

the biggest submatrix containing only negative numbers is

[[-11, -7],

 [-1, -9],

 [-3,-5]]

(left upper corner coordinates: 1,2, right lower corner coordinates: 3,3).

What's the most effective way to do it?

A brute force solution. Will work, but may be considered too slow for a bigger matrix:

mOrig = [[1,  -9, -2,   8,  6,  1],

    [8,  -1,-11,  -7,  6,  4],

    [10, 12, -1,  -9, -12, 14],

    [8, 10, -3,  -5,  17,  8],

    [6,  4, 10, -13, -16, 19]]



# reduce the problem

# now we have a matrix that contains only 0 and 1

# at the place where there was a negative number

# there is now a 1 and at the places where a positive

# number had been there is now a 0. 0s are considered

# to be negative numbers, if you want to change this,

# change the x < 0 to x <= 0.

m = [[1 if x < 0 else 0 for x in z] for z in mOrig]



# now we have the problem to find the biggest submatrix

# consisting only 1s.



# first a function that checks if a submatrix only contains 1s

def containsOnly1s(m, x1, y1, x2, y2):

    for i in range(x1, x2):

        for j in range(y1, y2):

            if m[i][j] == 0:

                return False

    return True



def calculateSize(x1, y1, x2, y2):

    return (x2 - x1) * (y2 - y1)



best = (-1, -1, -1, -1, -1)

for x1 in range(len(m)):

    for y1 in range(len(m[0])):

        for x2 in range(x1, len(m)):

            for y2 in range(y1, len(m[0])):

                if containsOnly1s(m, x1, y1, x2, y2):

                    sizeOfSolution = calculateSize(x1, y1, x2, y2)

                    if best[4] < sizeOfSolution:

                        best = (x1, y1, x2, y2, sizeOfSolution)



for x in range(best[0], best[2]):

    print("t".join([str(mOrig[x][y]) for y in range(best[1], best[3])]))

Will output

-11 -7

-1  -9

-3  -5

In case something else is meant with "biggest submatrix", the only function that needs to get changed is the following:

def calculateSize(x1, y1, x2, y2):

    return (x2 - x1) * (y2 - y1)

which is calculating the size of a submatrix.

Edit 1 ... first speedup

best = (-1, -1, -1, -1, -1)

for x1 in range(len(m)):

    for y1 in range(len(m[0])):

        if m[x1][y1] == 1: # The starting point must contain a 1

            for x2 in range(x1 + 1, len(m)): # actually can start with x1 + 1 here

                for y2 in range(y1 + 1, len(m[0])):

                    if containsOnly1s(m, x1, y1, x2, y2):

                        sizeOfSolution = calculateSize(x1, y1, x2, y2)

                        if best[4] < sizeOfSolution:

                            best = (x1, y1, x2, y2, sizeOfSolution)

                    else:

                        # There is at least one 0 in the matrix, so every greater

                        # matrix will also contain this 0

                        break

Edit 2

Ok, after converting the matrix into a matrix of 0 and 1 (as I do via the line m = [[1 if x < 0 else 0 for x in z] for z in mOrig] the problem is the same as what is called the maximal rectangle problem in literature. So I googled a bit about known algorithms for this kind of problem and came across this site here http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529 which is describing a very fast algorithm to solve this kind of problem. To summarize the points of this website, the algorithm is exploiting the structure. This can be done by using a stack in order to remember the structure profile which allows us to recalculate the width in case a narrow rectangle gets reused when an wider one gets closed.