Question

from typing import List

def longest_chain(submatrix: List[int]) -> int:
"""
Given a list of integers, return the length of the longest chain of 1's
that start from the beginning.

You MUST use a while loop for this! We will check.

>>> longest_chain([1, 1, 0])
2
>>> longest_chain([0, 1, 1])
0
>>> longest_chain([1, 0, 1])
1
"""
i = 0
a = []
while i < len(submatrix) and submatrix[i] != 0:
a.append(submatrix[i])
i += 1
return sum(a)

def largest_rectangle_at_position(matrix: List[List[int]], x: int, y: int
) -> int:
"""
Returns the area of the largest rectangle whose top left corner is at
position <x>, <y> in <matrix>.

You MUST make use of <longest_chain> here as you loop through each row
of the matrix. Do not modify the input matrix.

>>> case1 = [[1, 0, 1, 0, 0],
... [1, 0, 1, 1, 1],
... [1, 1, 1, 1, 1],
... [1, 0, 0, 1, 0]]
>>> largest_rectangle_at_position(case1, 0, 0)
4
>>> largest_rectangle_at_position(case1, 2, 0)
5
>>> largest_rectangle_at_position(case1, 1, 2)
6
"""
i = x + 1
if longest_chain(submatrix_row) > 1:
submatrices_row.append(submatrix_row)
while i < len(matrix):
submatrix_row = matrix[i][y:]
i += 1
if longest_chain(submatrix_row) > 1:
matrices_row.append(submatrix_row)
else:
for mat in submatrices_row:
if len(mat) == len(submatrices_row[0]):
area += sum(mat)
else:
return area
else:
submatrix_col = []
i = x
while i < len(matrix) and matrix[i][y] != 0:
submatrix_col.append(matrix[i][y])
i += 1
if longest_chain(submatrix_col) > 1:
area = sum(submatrix_col)
return area

def largest_rectangle_in_matrix(matrix: List[List[int]]) -> int:
"""
Returns the area of the largest rectangle in <matrix>.

The area of a rectangle is defined as the number of 1's that it contains.

Again, you MUST make use of <largest_rectangle_at_position> here. If you
managed to code largest_rectangle_at_position correctly, this function
should be very easy to implement.

Similarly, do not modify the input matrix.

Precondition:
<matrix> will only contain the integers 1 and 0.

>>> case1 = [[1, 0, 1, 0, 0],
... [1, 0, 1, 1, 1],
... [1, 1, 1, 1, 1],
... [1, 0, 0, 1, 0]]
>>> largest_rectangle_in_matrix(case1)
6
"""

pass

write the body of the function with the word pass

Answer 1

Code Screenshot :

Executable Code:

from typing import List

#Required function
def longest_chain(submatrix: List[int]) -> int:
   x = 0
   temp = []
   while x<len(submatrix) and submatrix[x] != 0:
       temp.append(submatrix[x])
       x += 1
   #Return the sum
   return sum(temp)

#Testing and Result

print(longest_chain([1, 1, 0]))
print(longest_chain([0, 1, 1]))
print(longest_chain([1, 0, 1]))
print()

Sample Output :