Help coderanch get a
new server
by contributing to the fundraiser
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Devaka Cooray
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• paul wheaton
• Henry Wong
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Tim Moores
• Carey Brown
• Mikalai Zaikin
Bartenders:
• Lou Hamers
• Piet Souris
• Frits Walraven

# Maximum Sum Project!!

Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
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 ]

Ranch Hand
Posts: 263
• Number of slices to send:
Optional 'thank-you' note:
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.

(instanceof Sidekick)
Posts: 8791
• Number of slices to send:
Optional 'thank-you' note:
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.
How about:

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
Greenhorn
Posts: 2
• Number of slices to send:
Optional 'thank-you' note:
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.

 Consider Paul's rocket mass heater.
reply