# 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 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 ]

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

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 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?

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