Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Maximum Sum Project!!

James Wa
Greenhorn
Posts: 2
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!!!

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

Tom Blough
Ranch Hand
Posts: 263
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
(instanceof Sidekick)
Ranch Hand
Posts: 8791
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?

(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:

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.