Почему не видит последний столбец

Question

Код в самом внизу.

У меня есть матрица размером n x m. В ней нужно найти подматрицу наибольшей площади состоящих из отрицательных чисел. Программа выводит координаты верхнего левого угла подматрицы и правого нижнего угла подматрицы. Например, у меня матрица

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

и вывод

1 2
3 3

Код работает, но в матрице, в которой последний столбец тоже состоит из отрицательных чисел, он не видит этот столбец, например эта матрица

-24 24 -44 -46 14 -64 -36
-32 -68 18 -60 -4 -30 -56
16 -6 -62 38 -54 2 0
-66 -22 32 30 -26 -56 -8
0 -62 -40 -16 -8 14 6
0 -78 0 -4 28 -18 -74
-22 -40 12 -54 32 -22 -44
-56 24 -72 30 10 34 -40
24 -62 4 -36 -32 -52 -10
-50 -8 -38 -64 14 32 -40
-80 0 -28 30 -58 -50 -56
-76 20 -52 -16 -54 -20 34
-42 -52 12 16 10 -20 20
-28 30 -52 -20 10 -6 -66
18 -40 -54 -28 -20 -68 36
20 -4 12 -22 -58 -26 -42
-60 -18 -34 -2 -58 -10 -16
36 8 -66 16 -14 30 28
-70 -10 -24 14 32 -14 -40
20 16 -22 10 -38 30 -66
-62 -52 -8 -34 -30 -8 -22
-70 14 -12 -50 -50 -52 -12
-66 -58 -10 -36 4 -64 -16
-70 22 -26 -50 10 18 -66
4 -4 -7 -10 -10 -3 -9
14 -7 -5 -4 -7 -7 -4
-50 -4 -4 -3 -4 -8 -8
10 -4 -9 -3 -7 -10 -7
-78 -9 -7 -8 -10 -4 -6
-22 -8 -5 -10 -10 -5 -10
-24 -5 -8 -8 -9 -9 -8
-78 -3 -5 -7 -5 -9 -10
-22 -9 -5 -5 -7 -5 -5
-50 -7 -9 -4 -7 -5 -8
-40 -3 -4 -3 -8 -6 -3
-8 -3 -9 -9 -3 -7 -6
-62 -8 -9 -9 -10 -9 -10
-12 -7 -7 -4 -10 -5 -10
-34 -9 -6 -8 -8 -9 -3
-50 -10 -9 -7 -6 -10 -8
-18 -5 -9 -9 -6 -5 -6
-66 -5 -10 -10 -7 -7 -3
-54 -9 -5 -5 -3 -8 -6
12 -4 -7 -5 -9 -5 -7
34 -8 -7 -6 -4 -5 -9
36 -9 -9 -10 -9 -9 -4
26 -9 -5 -6 -3 -5 -10
-24 -5 -6 -10 -6 -6 -5
-52 -10 -7 -7 -6 -3 -9
26 -6 -4 -7 -4 -5 -8
38 -10 -10 -7 -3 -9 -4
-4 -9 -9 -7 -6 -3 -7
30 -6 -8 -5 -4 -3 -6
20 -7 -3 -8 -9 -6 -8
14 -10 -3 -3 -8 -9 -7
-30 -10 -7 -3 -4 -3 -8
-52 -8 -7 -4 -6 -6 -3
-50 -8 -6 -9 -10 -6 -5
-64 -9 -8 -9 -5 -7 -3
-40 12 18 -58 -12 8 2
-34 24 -6 -2 -2 -40 -14
-10 -62 -26 -10 -48 -62 -8
16 8 -42 -76 -66 -68 -70
30 14 -56 -62 -62 -46 -2
28 -54 -42 -80 -40 -48 -66

у меня выводит

24 1
58 4

а нужно

24 1
58 6

В чем проблема?

Вот сам код

def maxAreaInMat(arr):
    best = 0
    bstart = 0
    blen = 0
    bhgt = 0
    stack = []
    for i in range(len(arr)):
        while (len(stack) > 0) and (arr[stack[-1]] >= arr[i]):
            smallest = arr[stack.pop()]
            if len(stack) == 0:
                start = 0
            else:
                start = stack[-1]+ 1
            #range_length * smallest_weight_in_range
            ar = smallest * (i - start)
            if ar > best:
                best = ar
                bstart = start
                blen = i - start
                bhgt = smallest
        stack.append(i)
    return best, bstart, blen, bhgt

def maxmat(A):
    r = len(A)
    c = len(A[0])
    for i in range(c):
        A[0][i] = 1 if A[0][i] < 0 else 0
    for y in range(1, r):
        for i in range(c):
            A[y][i] = 1 + A[y-1][i] if A[y][i] < 0 else 0
    maxarea = 0
    for y in range(r):
        best, bstart, blen, bhgt = maxAreaInMat(A[y])
        if best >= maxarea:
            maxarea = best
            y0, x0, y1, x1 = y - bhgt + 1, bstart, y, bstart + blen - 1
    print(y0, x0) 
    print(y1, x1)

def main():
    f = open("matrix.txt", "r")
    matrix=[]
    for line in f:
        matrix.append(list(map(int, line.split())))

    maxmat(matrix)


main()

Answer 1

Я так сделал, вроде работает, да и покороче чуть-чуть:

with open(r"d:\data.txt", "r") as file:
    matrix = [list(map(int, line.split())) for line in file]

height = len(matrix)
width = len(matrix[0])

c1, c2, square = (0, 0), (0, 0), 0

for j1 in range(height):
    for i1 in range(width):
        i2_max = width
        j2 = j1
        while j2 < height and matrix[j2][i1] < 0:

            i2 = i1
            while i2 < width and matrix[j2][i2] < 0:
                i2 += 1

            if i2 < i2_max:
                i2_max = i2

            j2 += 1

            if (i2_max - i1) * (j2 - j1) > square:
               square = (i2_max - i1) * (j2 - j1)
               c1 = (i1, j1)
               c2 = (i2_max - 1, j2 - 1)

print(c1, c2, square)

Answer 2

Вот моя реализация.

with open(r"matrix.txt", "r") as file:
    matrix = [list(map(lambda x: x[0]=='-', line.split())) for line in file]

height = len(matrix)
width = len(matrix[0])

c1, c2, area = (0, 0), (0, 0), 0

for row in range(height):
    for col in range(width):
            r, c = row, col
            while c < width and matrix[r][c]:
                c += 1
            
            while c > col and r < height:
                while r < height and all(matrix[r][col:c]):
                    r += 1
                a = (c - col) * (r - row)
                if a > area: c1, c2, area = (col, row), (c-1, r-1), a

                if r < height:
                    while c > col and not all(matrix[r][col:c]):
                        c -= 1
                    a = (c - col) * (r - row)
                    if a > area: c1, c2, area = (col, row), (c-1, r-1), a
                    
print(c1, c2, area)

БЛОГ НА HUSL

Почему не видит последний столбец

Ответы (2 шт):