Maximum Sum Project!!

[James Wa]

Hey! I'm a high school student currently taking AP Computer Science and I'm doing a project right now called Maximum Sum and I'm hopelessly stuck =( Could anyone please help me with this. Here's the question...
Given a 2-dimensional array of positive and negative integers, find the sb-rectangle with the largest sum. The sum of a sub-rectange rectangle is the sum of all the elements in that rectangle. The subrectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectange i any contiguous sub array of sixe 2x2 or great located within the whole array. For example, the maximal sub rectangle of the following is the lower left hand corner
0 -2 -7 0
9 2 -5 2
-4 1 -4 1
-1 8 0 -2
The sum of the lower left hand corner is 15
Input: The input consist of an rray of integers given from the keyboard. The input begisn entering hte size of the matrix (It does not have to be square)> This is folllowed by a reutr nand instruciton s for inputting the elements of the matrix
Output: The output cojnsist of printing the orginal matrix, the maximal sub-rectangle and the sum of that sub-rectangle. Be sure to label the output.
Whew, done typing that, well Here's what I currently have, I can input the matrix and I cna print it back out, but the actual part of figuring out how to find the max sum and then print the matrix of the max sum is confusing me!! It's probably not hard, but I've been tstuck for a while and any help would be great, like ideas or snippets of the progra... Here's what I have so far. Thanks to anyone who can help me!!!

package MaxSum;
import java.util.*;
import java.io.*;
public class Project1 {
public static void main(String[] args) {
try
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String oneLine;
int[][] intMat= inputMat();
System.out.println("\n" +"\n"+"The matrix is "+"\n");
printMat(intMat);
findMax(intMat);
}
catch(Exception e)
{
e.printStackTrace();
}
}
//Below is the input matrix
public static int [][]inputMat()
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int rowNum=0,colNum=0;
try
{
System.out.println("Enter the number of rows in your matrix");
rowNum=Integer.parseInt(in.readLine());
System.out.println("Enter the number of columns in your matrix");
colNum=Integer.parseInt(in.readLine());
}
catch(Exception e)
{
e.printStackTrace();
}
int [][]A= new int [rowNum][colNum];
try
{
String oneLine;
StringTokenizer str;
for (int row=0;row<A.length;row++)
{
int tokens = A[row].length;
System.out.println("Enter a row of "+tokens+" integers");
int flagInt = 0;
do
{
oneLine=in.readLine();
str = new StringTokenizer(oneLine);
flagInt=str.countTokens();
if(flagInt!=tokens)
{
System.out.println("Error! Need "+tokens+" integers");
continue;
}
}while(flagInt!=tokens);
str = new StringTokenizer(oneLine);
for(int col=0;col<A[row].length;col++)
{
A[row][col]=Integer.parseInt(str.nextToken());
}
}
}

catch(Exception e)
{
e.printStackTrace();
}
return A;
}

//Below method prints Matrix. It goes through the rows and columns. 
public static void printMat(int[][]A)
{
for(int row=0;row<A.length;row++)
{
for(int col=0;col<A[row].length;col++)
{
System.out.print(A[row][col]+"  ");
}
System.out.println();
}
}
//Below method figures the sum of the matrix
public static int MatrixSum(int[][]A)
{
int sum=0;
for(int row=0;row<A.length;row++)
{
for(int col=0;col<A[row].length;col++)
{
//This figures out the sum
sum+=A[row][col];
}
}
return sum;
}
//Below method figures out the max sum.
public static void findMax(int[][]A)
{
int length=2, width=2, posCol=0, posRow=0, subRow=0, subCol=0, tempSum=0;
do{
for(subRow=posRow;subRow<length;subRow++)
{
do{
for(subCol=posCol;subCol<width;subCol++)
{
tempSum+=A[subRow][subCol];
}
}while(length<A.length-2);
}
}while(width<A.length-2);
System.out.println(tempSum);

}
}

[ October 14, 2003: Message edited by: Jason Menard ]

[Tom Blough]

It looks like to me that you will have to loop through each element in the original matrix. At each element, construct all of the possible sub matricies (working to the right and then down) and calculate their sum.
For example (starting with element 1):
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20

starting with 01, we can construct the following
01 02
06 07
01 02 03
06 07 08
01 02 03 04
06 07 08 09
01 02 03 04 05
06 07 08 09 10
01 02
06 07
11 12
01 02 03
06 07 08
11 12 13
01 02 03 04
06 07 08 09
11 12 13 14
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
.
.
.
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
Then move on to element 02:
02 03
07 08
02 03 04
07 08 09
.
.
.
02 03
07 08
12 13
02 03 04
07 08 09
12 13 14
.
.
.

Then move on to element 3, then 4, then 5, then 6 ...
You'll notice that we can construct the matricies moving right and down. We don't have to worry about moving left and up because those matricies will have been calculated previously.
That is the alogrithm for calculating all possible sub matricies. You can do it with nested loops (or recursion if you've covered that in class). The other problem is keeping track of the results.
You really don't need to track ALL of the results, just the largest sum. So, at each sub matrix, calacuate the sum and compare to the current high value. If it's larger, save the sum as the new high value, and store the matrix that created it. When you finish all the sub matricies, the saved matrix and the high value will be the answer.
Hope this helps.

[Stan James]

One thing you'll want to do is keep track of the highest sum so far. As you test each sub-rectangle, if its sum is higher make it the new "highest". To help keep track of sub-rectangles, why not make a little class?

class Rectangle
{
   int mRow;   // top corner
   int mCol;   // left corner
   int mRows;  // height
   int mCols;  // width
   int mSum;   // sum
   public Rectangle( int aRow, int aCol, int aRows, int aCols)
   { mRow = aRow; mCol = aCol, etc ... }
}

(Some would tell you that since it has no methods it's a data structure and not a very nice class, but it will do the job.)
There is a neat approach to writing programs called Test Driven or Test First Development. What if you wrote this test:

int[][] myMatrix = new int[][]{{1,1},{1,1}};
Rectangle myRect = new Rectangle(1,1,2,2);
computeSum(Matrix, Rectangle);
if(Rectangle.mSum != 4) System.out.println("First test failed");

Could you write computeSum to make that work? (I believe you already have!) Then try more complex matrices and rectangles to make certain that compute is golden.
How about:

int[][] myMatrix = new int[][]{{1,1},{1,1}};
Set candidates = findAllRectangles(myMatrix);
if( candidates.length() != 1 ) ... error ...

Then bigger matrices with more rectangles. This would separately validate your logic for finding rectangles. I didn't follow every line of what you had, but it looked a bit suspect. I'd be happier with a test in hand to make sure it's golden, too.
Finally, loop through the Set of candidates and keep track of the highest sum found.
Now, since you're brand new to Java, suggesting additional classes and using Set (from the collection framework in the JDK) may be a bit advanced. Was that useful or just overwhelming?

[James Wa]

To Tom: Yea, that actualy helped quite a bit... Thank you! I'm working on something like that right now...
To Stan: Thanks for the attempt but we havn't learned any of that lol. It seems like an interesting idea though, if we get taught in calss I'l lbe sure to look back at this.