java - 二维数组中最有值(value)的图？

Question

问题是:

“一个二维整数数组将用于表示城市中每个街区的值(value)。该值可以是负数，表示该街区是拥有的责任。完成一个方法，找到最有值(value)的连续子的值(value)由二维数组表示的城市中的矩形。子矩形必须至少为 1 x 1。(如果所有值为负，“最有值(value)”矩形将是最接近 0 的负值。)

考虑以下示例。二维整数数组每行 6 行 5 列，代表城市的一个区域。周围有正方形的单元格代表给定数组中最有值(value)的连续子矩形。 (值为 15。)”

我完全不知道如何解决这个问题。我在想我可以从每一个值开始，用它制作每一个可能的子图，并更新一个变量以获得最高值。还有另一种方法吗？我不是在寻找答案，我只是需要一些指导。谢谢

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;

这是我目前的尝试。希望你们能看到我要去哪里。我从 0,0 开始检查整行并相应地更新。

Answer 1

该算法是探索所有矩形形状，并扫描该形状的城市。最大值出现在城市特定区域的特定形状中。

算法(假设城市是 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