-Can you please write this assignment as a program in java: Given an array (m x
ID: 3822245 • Letter: #
Question
-Can you please write this assignment as a program in java:
Given an array (m x n) of positive integers, find, in (mn) time, the maximum size square submatrix such that all values of the submatrix are larger than a given input k. For example, consider the following matrix
82 10 16 15 66
91 28 98 43 4
13 55 96 92 85
92 96 49 80 94
64 97 81 96 68
When k=3, the maximum submatrix is the entire matrix.
When k = 10, the maximum submatrix size is 4x4 with with (5,4)-th entry being the bottom right corner.
When k = 20, the maximum submatrix size is 3x3. There are three such submatrices whose bottom right corner coordinates are (4,4), (5,4), and (5,5), respectively.
When k = 50, the maximum submatrix size is 2x2. There are three such submatrices whose bottom right corner coordinates are (4,5), (5,2), and (5,5), respectively.
When k = 70, the maximum submatrix size is 2x2 with (4,5) being its bottom right corner coordinates.
Input: a text file of the integer matrix as in the above example, and a value k given by a user using the keyboard.
Output: the size of the maximum submatrix and the coordinates of the bottom right corner(s). In the above example for k=20, the output would be
3
4 4
5 4
5 5
Explanation / Answer
JAVA PROGRAM :
import java.util.Scanner;
public class Sample1 {
public static void main(String[] args) {
Scanner obj = new Scanner(System.in);
int n, m, k;
//Read n, m and k. Reading from console instead of file
n = obj.nextInt();
m = obj.nextInt();
k = obj.nextInt();
//This is important.
//Let dp[i][j] be the size at which there is a maximum square submatrix of size k ending at the position (i,j)
int dp[][] = new int[n + 1][m + 1];
int ans = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//Read the integer
int x = obj.nextInt();
if (x > k) {
//If that number is greater than k, then find the answer ending at this position.
dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
//Find the maximum answer
ans = Math.max(ans, dp[i][j]);
}
}
}
System.out.println(ans);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//Printing the position which has maximum answer
if (dp[i][j] == ans) {
System.out.println( i + " " + j );
}
}
}
}
}
OUTPUT 1 :
5 5 20
82 10 16 15 66
91 28 98 43 4
13 55 96 92 85
92 96 49 80 94
64 97 81 96 68
3
4 4
5 4
5 5
OUTPUT 2 :
5 5 10
82 10 16 15 66
91 28 98 43 4
13 55 96 92 85
92 96 49 80 94
64 97 81 96 68
4
5 4
OUTPUT 3 :
5 5 70
82 10 16 15 66
91 28 98 43 4
13 55 96 92 85
92 96 49 80 94
64 97 81 96 68
2
4 5
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.