Please help me get my code to run In Java, Given an array (m x n) of positive in

Question

Please help me get my code to run

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

This is the code I have

Explanation / Answer

I have created one method name "PrintMaxSubMatrix" which contains the functionality to check all the submatrix at a given input from the user.

I have attached the program along with the comments for each part of code.

Program:-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}
// Created a mehod along with the five parameters to calculate the submatrix

int PrintMaxSubMatrix(int** matx, int *topValue, int *leftValue, int *btmValue, int *rightValue, unsigned int SubMatx){
int i, j, k, totalMaxSumValue, totallocalMaxValue, retVal =0;
int **pointMax=NULL;
int *maxPosition=NULL, *sumValue = NULL;
*topValue = -1;
*leftValue = -1;
*btmValue = -1;
*rightValue = -1;
// Check the conditions using if-else statement

if (matx == NULL || SubMatx <= 0)
return -1;

pointMax = malloc (sizeof(int *) * SubMatx);
  
if (pointMax == NULL)
      
return -1;
      
   // Uses the for loop method to check the max value  
  
for (i = 0; i<SubMatx;i++)
{
  
pointMax[i]=malloc (sizeof(int)*SubMatx);
if (pointMax[i] == NULL) {
          
retVal = -1;
goto fail;
}
}
  
for (i = 0; i < SubMatx; i++) {
for (j = 0; j < SubMatx; j++) {
if (j == 0) {
pointMax[j][i] = matx[j][i];
} else {
pointMax[j][i] = matx[j][i] + pointMax[j - 1][i];
}
}
}
// It is object creation for finding top value in the array

totalMaxSumValue = matx[0][0];
*topValue = 0; *leftValue = 0; *btmValue = 0; *rightValue = 0;

sumValue = malloc(sizeof(int)*SubMatx);
if (sumValue == NULL){
retVal =-1;
goto fail;
}
   // it is useful for searching the maximum position obtained.
  
maxPosition = malloc(sizeof(int)*SubMatx);
if (maxPosition == NULL){
retVal =-1;
goto fail;
}
  
// Calculates the memsetfunction value to it

for (int i = 0; i < SubMatx; i++) {
for (int k = i; k < SubMatx; k++) {

matMemberSetval(sumValue, 0, SubMatx*sizeof(int));
matMemberSetval(maxPosition,0, SubMatx*sizeof(int));
totallocalMaxValue = 0;

sumValue[0] = pointMax[k][0] - (i==0 ? 0 : pointMax[i-1][0]);
for (int j = 1; j < SubMatx; j++) {
if (sumValue[j-1] > 0){
sumValue[j] = sumValue[j-1] + pointMax[k][j] - (i==0 ? 0 : pointMax[i-1][j]);
maxPosition[j] = maxPosition[j-1];
}else{
sumValue[j] = pointMax[k][j] - (i==0 ? 0 : pointMax[i-1][j]);
maxPosition[j] = j;
}
if (sumValue[j] > sumValue[totallocalMaxValue]){
totallocalMaxValue = j;
}
}

if (sumValue[totallocalMaxValue] > totalMaxSumValue){
  
totalMaxSumValue = sumValue[totallocalMaxValue];
*topValue = i;
*leftValue = maxPosition[totallocalMaxValue];
*btmValue = k;
*rightValue = totallocalMaxValue;
}
}
}

   // Print the statement using printf statment
  
for(i = *topValue; i <= *btmValue; i++){
for(int j = *leftValue; j <= *rightValue ; j++){
printf("%d ", matx[i][j]);
}
printf(" ");
}
  
fail:
for (j=0;j<SubMatx;j++) {
if (pointMax[i])
free(pointMax[i]);
}
if (pointMax)
free(pointMax);
if(maxPosition)
free(maxPosition);
if(sumValue)
free(sumValue);
return retVal;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.