Maximum Sum Project!!
James Wa
Greenhorn
Posts: 2
posted 13 years ago
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 2dimensional array of positive and negative integers, find the sbrectangle with the largest sum. The sum of a subrectange rectangle is the sum of all the elements in that rectangle. The subrectangle with the largest sum is referred to as the maximal subrectangle. A subrectange 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 subrectangle and the sum of that subrectangle. 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 ]
Given a 2dimensional array of positive and negative integers, find the sbrectangle with the largest sum. The sum of a subrectange rectangle is the sum of all the elements in that rectangle. The subrectangle with the largest sum is referred to as the maximal subrectangle. A subrectange 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 subrectangle and the sum of that subrectangle. 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
posted 13 years ago
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.
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.
Tom Blough<br /> <blockquote><font size="1" face="Verdana, Arial">quote:</font><hr>Cum catapultae proscriptae erunt tum soli proscripti catapultas habebunt.<hr></blockquote>
Stan James
(instanceof Sidekick)
Ranch Hand
Ranch Hand
Posts: 8791
posted 13 years ago
One thing you'll want to do is keep track of the highest sum so far. As you test each subrectangle, if its sum is higher make it the new "highest". To help keep track of subrectangles, 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?
(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?
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
James Wa
Greenhorn
Posts: 2
posted 13 years ago
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.
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.
Everybody's invited. Except this tiny ad:
the new thread boost feature brings a LOT of attention to your favorite threads
https://coderanch.com/t/674455/ThreadBoostfeature
