Most valuable plot in a 2D array?

Question

This is the problem:

"A 2d array of ints will be used to represent the value of each block in a city. The value could be negative indicating the block is a liability to own. Complete a method that finds the value of the most valuable contiguous sub rectangle in the city represented by the 2d array. The sub rectangle must be at least 1 by 1. (If all the values are negative "the most valuable" rectangle would be the negative value closest to 0.)

Consider the following example. The 2d array of ints has 6 rows and 5 columns per row, representing an area of the city. The cells with the square around it represent the most valuable contiguous sub rectangle in the given array. (Value of 15.)"

I am completely stumped as to how to go about solving this. I'm thinking that I could start on every single value and make every possible subplot with it and update a variable for the highest value. Is there another way of going about doing this? I'm not looking for the answer, I just need some guidance. Thanks

int most=-10000;
int current=0;
for(int i=0;i<city.length;i++){
    for(int j=0;j<city.length;j++){
        current+=city[i][j];
        if(current>most){
            most=current;
        }
    }
}

return most;

This is my attempt so far. Hopefully you guys can see where I'm going with it. I start at 0,0 and check the entire line and update most accordingly.

Try doing your way and then come back here if it doesn't work, and we'll help you with the problems in the code. This question is a bit too broad otherwise. — z7r1k3, Feb 02 '16 at 03:22
I'd start by playing with some brute-force algorithms and see what comes up. — Hovercraft Full Of Eels, Feb 02 '16 at 03:22
Well I just wanted to know if there were other more efficient ways of approaching the problem. Going through every single element would be very tedious and involve a lot of variables to check for conditions such as OutOfBounds exceptions. — Thandor7765, Feb 02 '16 at 03:25
But remember that computers don't mind tedious and in fact excel at it. You should be able to define and check for boundary conditions, and if not, debug the boundary errors that pop up in testing. — Hovercraft Full Of Eels, Feb 02 '16 at 03:26
We are graded on big O efficiency, which is why I'm looking for a more efficient way if there is one. This is one of the hardest problems I've run across in the course — Thandor7765, Feb 02 '16 at 03:27
YOU HAVE to brute force and check all values! Imagine your first row is -20, well that's the lowest your code has checked by far. The "Most" was 80, you can't tell it to ignore that second, third etc value, just because the first one is low. If there were some sort of average, or algorithm you knew, that each 2d array would have to follow, you can work with it. — christopher clark, Feb 02 '16 at 04:21
Have you take a look at [this](http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/)? — Pham Trung, Feb 02 '16 at 07:14
Possible duplicate of [Getting the submatrix with maximum sum?](http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum) — Pham Trung, Feb 02 '16 at 07:18

score 1 · Answer 1 · answered Feb 02 '16 at 04:59

1

The algorithm is to explore all rectangular shapes, and scan the city for that shape. The maximum value is found in a particular shape in a particular part of the city.

Algorithm (assume the city is NxM):

Set MAX = Lowest value in the city
// ROW / COL represent the shape of the rectangle
for ROW = 1 to N
 for COL = 1 to M
   // scan the city for a shape the size of ROWxCOL
   for POS_X = 0 to N-ROW
     for POS_Y = 0 to M-COL
       // You now have a top,left co-ordinate for the shape (POS_X,POS_Y)
       // This represents the position in the city[][] array
       SUM Values from co-ordinate POS_X,POS_Y to POS_X+ROW-1, POS_Y+COL-1
       IF SUM>MAX; MAX=SUM
PRINT MAX

answered Feb 02 '16 at 04:59

Ian Mc

5,656
4
18
25

even though it is the simplest solution, this solution will not score you much point for your assignment. – Mc Kevin Feb 02 '16 at 06:08
So this is a O(n^6) solution? – Pham Trung Feb 02 '16 at 07:15
should I use another for loop to SUM the values? – Thandor7765 Feb 02 '16 at 08:06
I managed to get it to work for the most part. My only problem is that when it is an array like int[][]={1,3,4,5,6,7,8}, it doesn't enter the loop – Thandor7765 Feb 02 '16 at 08:42
Is that array 2d? I don't think that is a valid city array. Other suggestions have been provided with at least an order of magnitude better time complexity. This was provided as a conceptual start. It is often the case that better algorithms emerge once you understand the brute force method. – Ian Mc Feb 02 '16 at 13:37

Most valuable plot in a 2D array?

1 Answers1