2 Q2 You are given an n x n matrix M[1..n, 1..n] of Os and 1s. A solid block in M is a submatrix of the form M[i..i', j..j'] in which all bits are equal to 1. A solid block is square if it has the same number of rows and columns. Now we allow rectangular blocks. Give a dynamic programming algorithm to find the maximum area of a solid block in M in O(n) time. (3 points) Define the subproblem that you will use to solve this problem. Define all the variables you introduce. (4 points) Give a recurrence which expresses the solution to each subproblem in terms of smaller subproblems. State any base case(s). (3 points) Write pseudocode for an algorithm to solve this problem. Your algorithm should run in O(n) time. 2 Q2 You are given an n x n matrix M[1..n, 1..n] of Os and 1s. A solid block in M is a submatrix of the form M[i..i', j..j'] in which all bits are equal to 1. A solid block is square if it has the same number of rows and columns. Now we allow rectangular blocks. Give a dynamic programming algorithm to find the maximum area of a solid block in M in O(n) time. (3 points) Define the subproblem that you will use to solve this problem. Define all the variables you introduce. (4 points) Give a recurrence which expresses the solution to each subproblem in terms of smaller subproblems. State any base case(s). (3 points) Write pseudocode for an algorithm to solve this problem. Your algorithm should run in O(n) time