# Thread: Help finding best submatrix

1. ## Help finding best submatrix

Hi everybody, i've got an assignment for thursday that i really cant work out, the exercise asks to find the best submatrix of a given matrix of nr rows and nc columns through a function int bestsubmatrix(int nr, int nc, double S[nr][nc], double m) that has to return the biggest submatrix of S[nr][nc] where the average of its elements doesnt have to exceed the value of m, example:

nr = 5, nc = 4, m = 2.6
matrix[nr][nc] = {
{ 5.69, 1.42, 2.70, 2.17 },
{ 2.07, 4.01, 2.78, 2.88 },
{ 6.84, 2.94, 2.96, 1.85 },
{ 1.83, 1.76, 5.64, 5.51 },
{ 6.31, 5.50, 4.26, 6.10 }
};
the function has to return 6, in fact 2.70 + 2.17 + 2.78 + 2.88 + 2.96 + 1.85 / 6 = 2.55 < m
till now thats what i was able to write:
Code:
```void bestsubmatrix(int nr, int nc, double S[nr][nc], double m)
{
int i, j, hold;
double sum = 0;

for(i = 0; i < nr; i++)
{
for(j = 1; j < nc; j++)
{
sum = sum + S[i][j] + S[i][j - 1];
if(sum / (j + 1) <= m)
{
hold = j;
printf("holding the %dth element of the row = %.2f\n", hold, S[i][hold]);
}
else
{
sum = 0;
}
}
}
}```
i made a void function so that i could use the printf, but i didnt get what i expected, any help would be appreciate, thanks

2. I thought an algorithm like this would work well:

1) walk each row
2) sum and average each two values
3) any two that meet this criteria, keep scanning until all the contiguous values in the row that meet the criteria, have been found.

4) at the starting column, then use the "flip" trick, to go down the column, continuing until all contiguous column values that meet the criteria, have been found.

5) when you've done this for all the values found in #3, then add up the values in this submatrix. rows = stop row - start row, cols = stop col - start col. total = rows * cols.

6) biggest total, wins.

I'm a hobby coder, so there may be a much better way to do this.

The "flip" trick is just putting the columns var in the inner nested loop
Code:
```for(col = 0; col < someVariable; col++) {
for(row = 0; row < someVariable; row++) {
//just something to do in a column
tally += grid[col][row];  //walk down a column in a 2D matrix.
}
}```

I thought an algorithm like this would work well:

1) walk each row
2) sum and average each two values
3) any two that meet this criteria, keep scanning until all the contiguous values in the row that meet the criteria, have been found.

4) at the starting column, then use the "flip" trick, to go down the column, continuing until all contiguous column values that meet the criteria, have been found.

5) when you've done this for all the values found in #3, then add up the values in this submatrix. rows = stop row - start row, cols = stop col - start col. total = rows * cols.

6) biggest total, wins.

I'm a hobby coder, so there may be a much better way to do this.

The "flip" trick is just putting the columns var in the inner nested loop
Code:
```for(col = 0; col < someVariable; col++) {
for(row = 0; row < someVariable; row++) {
//just something to do in a column
tally += grid[col][row];  //walk down a column in a 2D matrix.
}
}```
allright.. but I still dont get it at the first second and third step, after scanning each row and having found the sum and average of each two values, do i have to keep those whose average is less than m? I dont get the "keep scanning until all the contiguous values in the row that meet the criteria have been found", sorry but im quite new to C, thanks for the help anyway

4. Originally Posted by rob90
allright.. but I still dont get it at the first second and third step, after scanning each row and having found the sum and average of each two values, do i have to keep those whose average is less than m? I dont get the "keep scanning until all the contiguous values in the row that meet the criteria have been found", sorry but im quite new to C, thanks for the help anyway
I started a sample program, and quickly found the devil in the details. For example, say that none of the first row's averages came out less than m.

fine, fine.

Now you scan the 2nd row, and fine that the 4th, 5th, & 6th values, are less than m. And now you need to see whether, with these averages included, the 4th, 5th and 6th values from the *first* row, are now (after being averaged into the second rows average), also < m, and so should be included in the submatrix.

IMO, that makes the algorithm unusable unless you're a glutton for punishment - and I'd avoid using it unless you see some insight to simplify it.

OK, new algorithm. Simpler << yah! >>

Simple and fast, but not completely accurate:
You start with each value, and begin averaging the values in all 4 directions, with the adjacent index values.

When the average > m, you stop, and check the submatrix for "squareness (no stairstepping), and write the indexes to maxIndex string, if it's the largest so far.

While generally OK, this will fail when the data goes up over a "high spot" and then comes back down, later - because the high spot will stop your program from scanning further.

The accurate, but far more computationally intensive way:

for each element of the array, your program will generate every combination of row and column, index's, consistent with a square or rectangular array.

From that, generate every average that is possible for any size submatrix.

Largest one with an average < m, is the answer.

so, first off, we need to id every possible square or rectangular submatrix, for every element of the array.

00:
across
00 01
00 01 02
00 01 02 03

down
00 10
00 10 20
00 10 20 30
00 10 20 30 40

repeat for each element of the array.

Taking that data, calculate the average for each one.

Care must be taken to ensure that the submatrix is "squared off" so it's not stair-stepped, etc.

This seems like a logic be damned sort of problem. If you try to do it the first one (which seems reasonable at first glance), then you'll soon be tied up in logic knots galore.

Perhaps your instructor has mentioned some data structure or algorithm that is helpful for this.

Since the matrix is not large, and the submatrix has to be squared (which knocks off a lot of combinations right there), the simpler and comprehensive way seems best to me.

What do you think?

Since ... the submatrix has to be squared
Where do you read that? Sorry, I don't know about matrices, but can't a matrix be rectangular?

6. Originally Posted by hilarius
Where do you read that? Sorry, I don't know about matrices, but can't a matrix be rectangular?
Yes, of course. It can't be "stair-stepped" or weird shaped though. Square or rectangular == "squared", in my shorthand.

7. I finally made it, took more than 3 hours of intense work lol, had to use a brute force algorithm solution, trying all the sums of the submatrices of S through 4 different iterations, one that checks all the submatrices starting from the top-right corner of the main matrix, one that starts from the top-left corner, one from bottom right and the last one from bottom left, everytime it goes either up or down obviously, thanks for the help Adak, cheers

8. Congrats, Rob!

I finally went out on the web, looking for something elegant. I know matrices have been studied to death, but for some reason I couldn't find anything (free).

So I quit that and am just now coding up a brute force solution. It's anything *but* elegant, but it will do the job when it's done.

Three hours is good time for coding up a brute force solution, imo.