Я пытался решить проблему, чтобы найти местоположение (ytop, xtop, ybot, xbot) самого большого прямоугольника отрицательных целых чисел в матрице целых чисел. Я подошел к нему как к поиску самой большой области в гистограмме. Проблема заключается в следующем: для некоторых входных данных он возвращает правильный результат, но для некоторых (более крупных) результат перемещается на один столбец влево - обе координаты x на одну меньше, чем должны быть. Я буду рад, если кто-то обнаружит ошибку в моем коде или даже в комментариях.
Вот новый код:
from sys import argv
#text = argv[1]
text = "text2.txt"
# Finds the largest submatrix with only negative integers in a given matrix,
returns coordinates of its top left and bottom right corner.
def max_area(histogram):
# Finds the largest area in a histogram.
area = 0
stack = [-1]
for i in range(len(histogram)):
# Stores indeces of an ascending set of bars.
while stack[-1] != -1 and histogram[stack[-1]] >= histogram[i]:
# Finds a bar that is lower than the previous one, gets all
# possible areas from the bars before this (excluding).
last_element_index = stack.pop()
if area < histogram[last_element_index] * (i - stack[-1] - 1):
# The current area.
area = histogram[last_element_index] * (i - stack[-1] - 1)
# Index of the rightmost bar (from current area) = x of
bottom right corner.
x_bot = last_element_index
# Value (height) of the rightmost bar = height of the area.
height = histogram[last_element_index]
# Index of current bar - 1 = the last ascending bar, -
# stack[-1] = amount of bars between <-- and the bar that's
# being looked at.
width = i - stack[-1] - 1
stack.append(i)
while stack[-1] != -1:
last_element_index = stack.pop()
if area < histogram[last_element_index] * (i - stack[-1] - 1):
area = histogram[last_element_index] * (i - stack[-1] - 1)
x_bot = last_element_index + 1
width = i - stack[-1] - 1
return area, x_bot, height, width
large_location = [0, 0, 0, 0] # ytop, xtop, ybot, xbot
large_size = 0
with open(text) as file:
row = file.readline().split()
histogram = []
row_number = 0
# Creates the 1st histogram, to know its lenght. Stores positive and
# negative integers as 0's and 1's.
for number in row:
if number[0] == "-":
histogram.append(1)
else:
histogram.append(0)
large_size, large_location[3], height, width = max_area(histogram)
# size, xbot, height, width
large_location[2] = row_number # ybot
large_location[0] = large_location[2] - height + 1 # ytop
large_location[1] = large_location[3] - width + 1 # xtop
for row in file:
# Stores the index of the current row, used for the bottom y coordinate.
row_number += 1
aux = row.split()
# For every row in the matrix, if a number is positive sets the
# corresponding value inthe histogram to 0,
# else adds 1. The histogram always represents all the uninterupted
# negative integers in rows 0 to current.
for i in range(len(aux)):
if aux[i][0] == "-":
histogram[i] += 1
else:
histogram[i] = 0
# Gets the max area of the current histogram, compares it to the
# previous best result, stores it when neccessary.
current_size = max_area(histogram)
if current_size[0] > large_size:
large_size, large_location[3], height, width = current_size
large_location[2] = row_number
large_location[0] = large_location[2] - height + 1
large_location[1] = large_location[3] - width + 1
print(large_location[0], large_location[1])
print(large_location[2], large_location[3])
#print("size:", large_size, "height:", height, "width:", width)
Это дает правильный результат [1, 2, 3, 3].
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
Я не хочу публиковать пример плохого, потому что в нем более 50 столбцов, но результат выглядит так [11, 33, 23, 51] вместо [11, 34, 23, 52].