Получение подматрицы с максимальной суммой?

Ответ 1

О восстановлении фактической подматрицы, а не только максимальной суммы, вот что я получил. Извините, у меня нет времени перевести мой код на вашу версию java, поэтому я отправляю свой код Ruby с комментариями в ключевых частях

def max_contiguous_submatrix_n3(m)
  rows = m.count
  cols = rows ? m.first.count : 0

  vps = Array.new(rows)
  for i in 0..rows
    vps[i] = Array.new(cols, 0)
  end

  for j in 0...cols
    vps[0][j] = m[0][j]
    for i in 1...rows
      vps[i][j] = vps[i-1][j] + m[i][j]
    end
  end

  max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right]
  # these arrays are used over Kandane
  sum = Array.new(cols) # obvious sum array used in Kandane
  pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j

  for i in 0...rows
    for k in i...rows
      # Kandane over all columns with the i..k rows
      sum.fill(0) # clean both the sum and pos arrays for the upcoming kandane
      pos.fill(0)
      local_max = 0 # we keep track of the position of the max value over each Kandane execution
      # notice that we do not keep track of the max value, but only its position
      sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0])
      for j in 1...cols
        value = vps[k][j] - (i==0 ? 0 : vps[i-1][j])
        if sum[j-1] > 0
          sum[j] = sum[j-1] + value
          pos[j] = pos[j-1]
        else
          sum[j] = value
          pos[j] = j
        end
        if sum[j] > sum[local_max]
          local_max = j
        end
      end
      # Kandane ends here

      # Here the key thing
      # If the max value obtained over the past kandane execution is larger than
      # the current maximum, then update the max array with sum and bounds
      if sum[local_max] > max[0]
        # sum[local_max] is the new max value
        # the corresponding submatrix goes from rows i..k.
        # and from columns pos[local_max]..local_max
        # the array below contains [max_sum,top,left,bottom,right]
        max = [sum[local_max], i, pos[local_max], k, local_max]
      end
    end
  end

  return max # return the array with [max_sum,top,left,bottom,right]
end

Некоторые примечания для пояснения:

Я использую массив для хранения всех значений, относящихся к результату, для удобства. Вы можете просто использовать пять автономных переменных: max, top, left, bottom, right. Это просто проще назначить в одной строке массиву, а затем подпрограмма возвращает массив со всей необходимой информацией.

Если вы скопируете и вставьте этот код в текстовый редактор с поддержкой Ruby, вы, очевидно, поймете его лучше. Надеюсь, это поможет!

Ответ 2

Вот объяснение, чтобы пойти с опубликованным кодом. Для эффективного выполнения этой работы есть два ключевых метода: (I) алгоритм Кандана и (II) с использованием префиксных сумм. Вам также необходимо (III) применить трюки к матрице.

Часть I: алгоритм Кандана

Алгоритм Кандане - это способ найти непрерывную подпоследовательность с максимальной суммой. Давайте начнем с подхода грубой силы для нахождения максимальной непрерывной подпоследовательности, а затем рассмотрим ее оптимизацию для получения алгоритма Кандана.

Предположим, что у вас есть последовательность:

-1,  2,  3, -2

Для подхода грубой силы пройдите по последовательности, генерирующей все возможные подпоследовательности, как показано ниже. Учитывая все возможности, мы можем начинать, расширять или заканчивать список с каждым шагом.

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
Possible subsequences:
-1   [sum -1]

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
Possible subsequences:
-1 (end)      [sum -1]
-1,  2        [sum  1]
 2            [sum  2]

At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
Possible subsequences:
-1, (end)       [sum -1]
-1,  2 (end)    [sum -1]
 2 (end)        [sum 2]
-1,  2,  3      [sum 4]
 2,  3          [sum 5]
 3              [sum 3]

At index 3, we consider appending the -2
-1,  2,  3, -2
             ^
Possible subsequences:
-1, (end)          [sum -1]
-1,  2 (end)       [sum  1]
 2 (end)           [sum  2]
-1,  2  3 (end)    [sum  4]
 2,  3 (end)       [sum  5]
 3, (end)          [sum  3]
-1,  2,  3, -2     [sum  2]
 2,  3, -2         [sum  3]
 3, -2             [sum  1]
-2                 [sum -2]

Для этого подхода грубой силы мы, наконец, выбираем список с лучшей суммой, (2, 3) и этот ответ. Однако, чтобы сделать это эффективным, считайте, что вам действительно не нужно хранить каждый из списков. Из списков, которые еще не закончились, вам нужно только сохранить лучший, другие не могут сделать лучше. Из списков, которые закончились, вам может понадобиться сохранить только лучший, и только если он лучше, чем те, которые еще не закончились.

Итак, вы можете отслеживать, что вам нужно, только с помощью массива позиций и массива сумм. Массив позиции определяется следующим образом: position[r] = s отслеживает список, заканчивающийся на r, и начинается с s. И sum[r] дает сумму для подпоследовательности, заканчивающейся на index r. Это оптимизированный подход - алгоритм Кандана.

Выполнение примера снова отслеживает наш прогресс таким образом:

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2


At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5

Again, we choose to extend because that gives a higher sum that starting a new one.
-1,  2,  3, -2
             ^
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5
positions[3] = 3     sum[3] = 3

Опять же, лучшая сумма равна 5, а список - от индекса 1 до индекса 2, который равен (2, 3).

Часть II: суммы префикса

Мы хотим иметь способ вычислить сумму по строке, для любой начальной точки для любой конечной точки. Я хочу вычислить эту сумму в O (1) раз, а не просто добавлять, что принимает O (m) время, где m - количество элементов в сумме. С некоторыми предварительными вычислениями это может быть достигнуто. Вот как. Предположим, у вас есть матрица:

a   d   g
b   e   h 
c   f   i

Вы можете прекомпретировать эту матрицу:

a      d      g
a+b    d+e    g+h
a+b+c  d+e+f  g+h+i

Как только это будет сделано, вы можете получить сумму, идущую вдоль любого столбца от любой начальной до конечной точки в столбце, просто вычитая два значения.

Часть III. Объединяя трюки, чтобы найти максимальную подматрицу

Предположим, что вы знаете верхнюю и нижнюю строки максимальной подматрицы. Вы можете сделать это:

• Игнорировать строки над верхней строкой и игнорировать строки внизу строки.
• С какой матрицей осталось, рассмотрим используемую сумму каждого столбца для сформируйте последовательность (вроде строки, которая представляет несколько строк). (Вы можете быстро вычислить любой элемент этой последовательности с помощью префикса суммы).
• Используйте подход Kandane для определения лучшей подпоследовательности в этом последовательность. Индексы, которые вы получите, скажут вам слева и справа позиции лучшей подматрицы.

Теперь как насчет того, чтобы определить верхнюю и нижнюю строку? Просто попробуйте все возможности. Попытайтесь положить верх в любом месте, где можете, и поместив его в любом месте, и запустите процедуру Kandane-base, описанную ранее для каждой возможности. Когда вы находите максимальное значение, вы отслеживаете верхнее и нижнее положение.

Поиск строки и столбца принимает O (M ^ 2), где M - количество строк. Поиск столбца принимает O (N) время, где N - количество столбцов. Таким образом, общее время равно O (M ^ 2 * N). И, если M = N, требуется время O (N ^ 3).

Ответ 3

Есть уже много ответов, но вот еще одна реализация Java, которую я написал. Он сравнивает 3 решения:

• Наивное (грубая сила) - O (n ^ 6) время
• Очевидное решение DP - O (n ^ 4) время и O (n ^ 3) пространство
• Более умное решение DP на основе алгоритма Кадане - O (n ^ 3) и O (n ^ 2) space

Есть примеры пробегов для n = 10 до n = 70 с шагом 10 с хорошим выходом, сравнивающим время выполнения и требования к пространству.

код:

public class MaxSubarray2D {

    static int LENGTH;
    final static int MAX_VAL = 10;

    public static void main(String[] args) {

        for (int i = 10; i <= 70; i += 10) {
            LENGTH = i;

            int[][] a = new int[LENGTH][LENGTH];

            for (int row = 0; row < LENGTH; row++) {
                for (int col = 0; col < LENGTH; col++) {
                    a[row][col] = (int) (Math.random() * (MAX_VAL + 1));
                    if (Math.random() > 0.5D) {
                        a[row][col] = -a[row][col];
                    }
                    //System.out.printf("%4d", a[row][col]);
                }
                //System.out.println();
            }
            System.out.println("N = " + LENGTH);
            System.out.println("-------");

            long start, end;
            start = System.currentTimeMillis();
            naiveSolution(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   no auxiliary space requirements");
            start = System.currentTimeMillis();
            dynamicProgammingSolution(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   requires auxiliary space for "
                    + ((int) Math.pow(LENGTH, 4)) + " integers");
            start = System.currentTimeMillis();
            kadane2D(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   requires auxiliary space for " +
                    + ((int) Math.pow(LENGTH, 2)) + " integers");
            System.out.println();
            System.out.println();
        }
    }

    // O(N^2) !!!
    public static void kadane2D(int[][] a) {
        int[][] s = new int[LENGTH + 1][LENGTH]; // [ending row][sum from row zero to ending row] (rows 1-indexed!)
        for (int r = 0; r < LENGTH + 1; r++) {
            for (int c = 0; c < LENGTH; c++) {
                s[r][c] = 0;
            }
        }
        for (int r = 1; r < LENGTH + 1; r++) {
            for (int c = 0; c < LENGTH; c++) {
                s[r][c] = s[r - 1][c] + a[r - 1][c];
            }
        }
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;
        for (int r1 = 1; r1 < LENGTH + 1; r1++) { // rows 1-indexed!
            for (int r2 = r1; r2 < LENGTH + 1; r2++) { // rows 1-indexed!
                int[] s1 = new int[LENGTH];
                for (int c = 0; c < LENGTH; c++) {
                    s1[c] = s[r2][c] - s[r1 - 1][c];
                }
                int max = 0;
                int c1 = 0;
                for (int c = 0; c < LENGTH; c++) {
                    max = s1[c] + max;
                    if (max <= 0) {
                        max = 0;
                        c1 = c + 1;
                    }
                    if (max > maxSum) {
                        maxSum = max;
                        maxRowStart = r1 - 1;
                        maxColStart = c1;
                        maxRowEnd = r2 - 1;
                        maxColEnd = c;
                    }
                }
            }
        }

        System.out.print("KADANE SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }

    // O(N^4) !!!
    public static void dynamicProgammingSolution(int[][] a) {
        int[][][][] dynTable = new int[LENGTH][LENGTH][LENGTH + 1][LENGTH + 1]; // [row][col][height][width]
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 0; h < LENGTH + 1; h++) {
                    for (int w = 0; w < LENGTH + 1; w++) {
                        dynTable[r][c][h][w] = 0;
                    }
                }
            }
        }

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 1; h <= LENGTH - r; h++) {
                    int rowTotal = 0;
                    for (int w = 1; w <= LENGTH - c; w++) {
                        rowTotal += a[r + h - 1][c + w - 1];
                        dynTable[r][c][h][w] = rowTotal + dynTable[r][c][h - 1][w];
                    }
                }
            }
        }

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 0; h < LENGTH + 1; h++) {
                    for (int w = 0; w < LENGTH + 1; w++) {
                        if (dynTable[r][c][h][w] > maxSum) {
                            maxSum = dynTable[r][c][h][w];
                            maxRowStart = r;
                            maxColStart = c;
                            maxRowEnd = r + h - 1;
                            maxColEnd = c + w - 1;
                        }
                    }
                }
            }
        }

        System.out.print("    DP SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }


    // O(N^6) !!!
    public static void naiveSolution(int[][] a) {
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;

        for (int rowStart = 0; rowStart < LENGTH; rowStart++) {
            for (int colStart = 0; colStart < LENGTH; colStart++) {
                for (int rowEnd = 0; rowEnd < LENGTH; rowEnd++) {
                    for (int colEnd = 0; colEnd < LENGTH; colEnd++) {
                        int sum = 0;
                        for (int row = rowStart; row <= rowEnd; row++) {
                            for (int col = colStart; col <= colEnd; col++) {
                                sum += a[row][col];
                            }
                        }
                        if (sum > maxSum) {
                            maxSum = sum;
                            maxRowStart = rowStart;
                            maxColStart = colStart;
                            maxRowEnd = rowEnd;
                            maxColEnd = colEnd;
                        }
                    }
                }
            }
        }

        System.out.print(" NAIVE SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }

}

Ответ 4

Вот версия Java версии Ernesto с некоторыми изменениями:

public int[][] findMaximumSubMatrix(int[][] matrix){
    int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }

    int maxSum = matrix[0][0];
    int top = 0, left = 0, bottom = 0, right = 0; 

    //Auxiliary variables 
    int[] sum = new int[dim];
    int[] pos = new int[dim];
    int localMax;                        

    for (int i = 0; i < dim; i++) {
        for (int k = i; k < dim; k++) {
            // Kandane over all columns with the i..k rows
            reset(sum);
            reset(pos);
            localMax = 0;
            //we keep track of the position of the max value over each Kandane execution
            // notice that we do not keep track of the max value, but only its position
            sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
            for (int j = 1; j < dim; j++) {                    
                if (sum[j-1] > 0){
                    sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = pos[j-1];
                }else{
                    sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = j;
                }
                if (sum[j] > sum[localMax]){
                    localMax = j;
                }
            }//Kandane ends here

            if (sum[localMax] > maxSum){
                  /* sum[localMax] is the new max value
                    the corresponding submatrix goes from rows i..k.
                     and from columns pos[localMax]..localMax
                     */
                maxSum = sum[localMax];
                top = i;
                left = pos[localMax];
                bottom = k;
                right = localMax;
            }      
        }
    }
    System.out.println("Max SubMatrix determinant = " + maxSum);
    //composing the required matrix
    int[][] output = new int[bottom - top + 1][right - left + 1];
    for(int i = top, k = 0; i <= bottom; i++, k++){
        for(int j = left, l = 0; j <= right ; j++, l++){                
            output[k][l] = matrix[i][j];
        }
    }
    return output;
}

private void reset(int[] a) {
    for (int index = 0; index < a.length; index++) {
        a[index] = 0;
    }
}

Ответ 5

С помощью Algorithmist и Ларри и модификации алгоритма Кадане, вот мое решение:

int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }
    int maxSoFar = 0;
    int min , subMatrix;
    //iterate over the possible combinations applying Kadane Alg.
    for (int i = 0; i < dim; i++) {
        for (int j = i; j < dim; j++) {
            min = 0;
            subMatrix = 0;
            for (int k = 0; k < dim; k++) {
                if (i == 0) {
                    subMatrix += ps[j][k];
                } else {
                    subMatrix += ps[j][k] - ps[i - 1 ][k];
                }
                if(subMatrix < min){
                    min = subMatrix;
                }
                if((subMatrix - min) > maxSoFar){
                    maxSoFar = subMatrix - min;
                }                    
            }
        }
    }

Остается только определить элементы подматрицы, т.е. верхний левый и правый нижний угол подматрицы. Любое предложение?

Ответ 6

Я собираюсь опубликовать ответ здесь и могу добавить фактический код С++, если он запрошен, потому что я недавно проработал это. Некоторые слухи о разрыве и завоевании, которые могут решить это в O (N ^ 2), есть, но я не видел никакого кода, чтобы поддержать это. По моему опыту, вот что я нашел.

    O(i^3j^3) -- naive brute force method
    o(i^2j^2) -- dynamic programming with memoization
    O(i^2j)   -- using max contiguous sub sequence for an array


if ( i == j ) 
O(n^6) -- naive
O(n^4) -- dynamic programming 
O(n^3) -- max contiguous sub sequence

Ответ 7

Посмотрите JAMA package; Я считаю, что это облегчит вашу жизнь.

Ответ 8

Вот решение С#. Ссылка: http://www.algorithmist.com/index.php/UVa_108

public static MaxSumMatrix FindMaxSumSubmatrix(int[,] inMtrx)
{
    MaxSumMatrix maxSumMtrx = new MaxSumMatrix();

    // Step 1. Create SumMatrix - do the cumulative columnar summation 
    // S[i,j] = S[i-1,j]+ inMtrx[i-1,j];
    int m = inMtrx.GetUpperBound(0) + 2;
    int n = inMtrx.GetUpperBound(1)+1;
    int[,] sumMatrix = new int[m, n];

    for (int i = 1; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            sumMatrix[i, j] = sumMatrix[i - 1, j] + inMtrx[i - 1, j];
        }
    }

    PrintMatrix(sumMatrix);

    // Step 2. Create rowSpans starting each rowIdx. For these row spans, create a 1-D array r_ij            
    for (int x = 0; x < n; x++)
    {
        for (int y = x; y < n; y++)
        {
            int[] r_ij = new int[n];

            for (int k = 0; k < n; k++)
            {
                r_ij[k] = sumMatrix[y + 1,k] - sumMatrix[x, k];
            }

            // Step 3. Find MaxSubarray of this r_ij. If the sum is greater than the last recorded sum =>
            //          capture Sum, colStartIdx, ColEndIdx.
            //          capture current x as rowTopIdx, y as rowBottomIdx.
            MaxSum currMaxSum = KadanesAlgo.FindMaxSumSubarray(r_ij);

            if (currMaxSum.maxSum > maxSumMtrx.sum)
            {
                maxSumMtrx.sum = currMaxSum.maxSum;
                maxSumMtrx.colStart = currMaxSum.maxStartIdx;
                maxSumMtrx.colEnd = currMaxSum.maxEndIdx;
                maxSumMtrx.rowStart = x;
                maxSumMtrx.rowEnd = y;
            }
        }
    }

    return maxSumMtrx;
}

public static void PrintMatrix(int[,] matrix)
{
    int endRow = matrix.GetUpperBound(0);
    int endCol = matrix.GetUpperBound(1);
    PrintMatrix(matrix, 0, endRow, 0, endCol);
}

public static void PrintMatrix(int[,] matrix, int startRow, int endRow, int startCol, int endCol)
{
    StringBuilder sb = new StringBuilder();
    for (int i = startRow; i <= endRow; i++)
    {
        sb.Append(Environment.NewLine);
        for (int j = startCol; j <= endCol; j++)
        {
            sb.Append(string.Format("{0}  ", matrix[i,j]));
        }
    }

    Console.WriteLine(sb.ToString());
}

// Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum
public static MaxSum FindMaxSumSubarray(int[] inArr)
{
    int currMax = 0;
    int currStartIndex = 0;
    // initialize maxSum to -infinity, maxStart and maxEnd idx to 0.

    MaxSum mx = new MaxSum(int.MinValue, 0, 0);

    // travers through the array
    for (int currEndIndex = 0; currEndIndex < inArr.Length; currEndIndex++)
    {
        // add element value to the current max.
        currMax += inArr[currEndIndex];

        // if current max is more that the last maxSum calculated, set the maxSum and its idx
        if (currMax > mx.maxSum)
        {
            mx.maxSum = currMax;
            mx.maxStartIdx = currStartIndex;
            mx.maxEndIdx = currEndIndex;
        }

        if (currMax < 0) // if currMax is -ve, change it back to 0
        {
            currMax = 0;
            currStartIndex = currEndIndex + 1;
        }
    }

    return mx;
}

struct MaxSum
{
    public int maxSum;
    public int maxStartIdx;
    public int maxEndIdx;

    public MaxSum(int mxSum, int mxStart, int mxEnd)
    {
        this.maxSum = mxSum;
        this.maxStartIdx = mxStart;
        this.maxEndIdx = mxEnd;
    }
}

class MaxSumMatrix
{
    public int sum = int.MinValue;
    public int rowStart = -1;
    public int rowEnd = -1;
    public int colStart = -1;
    public int colEnd = -1;
}

Ответ 9

это моя реализация 2D алгоритма Кадане. Я думаю, что это более понятно. Концепция основана на просто алгоритме kadane. Первый и второй петли основной части (то есть в нижней части кода) состоит в том, чтобы выбрать каждую комбинацию строк, а третий цикл - использовать алгоритм 1D kadane по каждой следующей сумме столбцов (которая может быть вычислена в const time, потому что предварительной обработки матрицы путем вычитания значений из двух выбранных (из комбинаций) строк). Вот код:

    int [][] m = {
            {1,-5,-5},
            {1,3,-5},
            {1,3,-5}
    };
    int N = m.length;

    // summing columns to be able to count sum between two rows in some column in const time
    for (int i=0; i<N; ++i)
        m[0][i] = m[0][i];
    for (int j=1; j<N; ++j)
        for (int i=0; i<N; ++i)
            m[j][i] = m[j][i] + m[j-1][i];

    int total_max = 0, sum;
    for (int i=0; i<N; ++i) {
        for (int k=i; k<N; ++k) { //for each combination of rows
            sum = 0;
            for (int j=0; j<N; j++) {       //kadane algorithm for every column
                sum += i==0 ? m[k][j] : m[k][j] - m[i-1][j]; //for first upper row is exception
                total_max = Math.max(sum, total_max);
            }
        }
    }

    System.out.println(total_max);

Ответ 10

Вот мое решение. Оно O (n ^ 3) во времени и O (n ^ 2). https://gist.github.com/toliuweijing/6097144

// 0th O(n) on all candidate bottoms @B.
// 1th O(n) on candidate tops @T.
// 2th O(n) on finding the maximum @left/@right match.
int maxRect(vector<vector<int> >& mat) {
    int n               = mat.size();
    vector<vector<int> >& colSum = mat;

    for (int i = 1 ; i < n ; ++i) 
    for (int j = 0 ; j < n ; ++j)
        colSum[i][j] += colSum[i-1][j];

    int optrect = 0;
    for (int b = 0 ; b < n ; ++b) {
        for (int t = 0 ; t <= b ; ++t) {
            int minLeft = 0;
            int rowSum[n];
            for (int i = 0 ; i < n ; ++i) {
                int col = t == 0 ? colSum[b][i] : colSum[b][i] - colSum[t-1][i];
                rowSum[i] = i == 0? col : col + rowSum[i-1];
                optrect = max(optrect, rowSum[i] - minLeft); 
                minLeft = min(minLeft, rowSum[i]);
            }
        }
    }

    return optrect;
}

Ответ 11

Я бы просто проанализировал массив NxN, удалив -ve независимо от того, что остается наивысшей суммой подматрицы.

В вопросе не говорится, что вам нужно оставить исходную матрицу неповрежденной или что порядок имеет значение.