How to find the largest subarray of negative numbers in a 2D array?

Question

Python

Hello,
I am given a 2D matrix consisting of positive and negative numbers at the input.
I need to find the largest submatrix of negative numbers and return the coordinates of the top left and bottom right corners.
I found many solutions on the Internet for a similar problem, but I can’t translate it into what I need ..
Since time is limited, I need to come up with some faster algorithm than Brute Force, but unfortunately nothing comes to mind .. Please help.
Example
Login

• 
  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
  

Output

• 
  1 2
  3 3
  

Answer 1

Wrote a rather productive solution on convolutions. Filter2d from OpenCV is used to calculate the conv conv of the mask matrix with the kernel kernel, but this function can be replaced with a similar one from any other mathematical library - you need to see which is faster. It is also important that the calculations are made in float32, and not in integers - this is orders of magnitude (!) Faster.

import cv2
import numpy as np

data = """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"""

# matrix = np.random.randint(-128, 128, (1000, 1000), dtype=np.int32)
matrix = np.int32([line.split() for line in data.splitlines()])

def find_max_kernel(matrix, border=cv2.BORDER_ISOLATED):
    max_area = 0
    mask = np.float32(matrix < 0)
    ones = np.ones_like(mask)
    conv_x = np.zeros_like(mask)
    conv_y = np.zeros_like(mask)
    max_h, max_w = mask.shape
    for h in range(1, max_h + 1):
        cv2.filter2D(mask, -1, ones[:h, None, 0], conv_y, (0, 0), 0, border)
        for w in range(1, max_w + 1):
            area = h * w
            if area > max_area:
                cv2.filter2D(conv_y, -1, ones[None, 0, :w], conv_x, (0, 0), 0, border)
                if conv_x.max() == area:
                    max_area, shape = area, (h, w)
                else:
                    if w == 1:
                        max_h = h - 1
                    if h == 1:
                        max_w = w - 1
                    break
        if h >= max_h:
            break
    cv2.filter2D(mask, -1, np.ones(shape, np.float32), conv_x, (0, 0), 0, border)
    p1 = np.array(np.unravel_index(conv_x.argmax(), conv_x.shape))
    p2 = p1 + shape - 1            
    return p1, p2

print(*find_max_kernel(matrix), sep='\n')

A 1000 x 1000 matrix on my 2 cores is processed in an average of 82 ms:
An example of applying the algorithm: the largest sub-matrix is ​​found - an inscribed square

Answer 2

https://tproger.ru/problems/max-sum-submatrix/

Answer 3

https://stackoverflow.com/questions/53252626/findi...