найти самую большую подматрицу, полную единиц в линейном времени

Question

Учитывая n на n матрицу с нулями и единицами, найдите наибольшую подматрицу, полную единиц в линейном времени.Мне сказали, что существует решение с O (n) сложностью по времени.Если в матрице X n имеется n ^ 2 элементов, как существует линейное решение?

Answer 1

Если у вас нет нестандартного определения подматрицы, эта проблема является NP-сложной из-за уменьшения от максимальной клики.

Answer 2

Вы не можете найти матрицу n x n за n время. Контрпример: матрица нулей с единичным элементом, равным единице. Вы должны проверить каждый элемент, чтобы найти его, поэтому время должно быть не менее O(n^2).

Теперь, если вы говорите, что матрица имеет N = n^2 записей, и вы рассматриваете только подматрицы, которые образуют непрерывный блок, то вы сможете найти самую большую подматрицу, проходя по диагонали по матрице, отслеживая каждого прямоугольника из них, как вы идете. В общем, вы можете одновременно иметь до O(sqrt(N)) активных прямоугольников, и вам нужно будет искать в них, чтобы выяснить, какой прямоугольник был самым большим, поэтому вы должны быть в состоянии сделать это за O(N^(3/2) * log(N)) время.

Если вы можете выбрать произвольные строки и столбцы для формирования вашей подматрицы, то я не вижу никакого очевидного алгоритма полиномиального времени.

Answer 3

public static int biggestSubMatrix(int[][] matrix) {

    int[][] newMatrix = new int[matrix.length][matrix[0].length];

    for (int i = 0; i < matrix.length; i++) {
        int sum = 0;
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 1) {
                sum++;
                newMatrix[i][j] = sum;
            } else {
                sum = 0;
                newMatrix[i][j] = 0;
            }
        }
    }


    int maxDimention = 0;
    int maxSubMatrix = 0;

    for (int i = 0; i < newMatrix[0].length; i++) {
        //find dimention for each column
        maxDimention = calcHighestDimentionBySmallestItem(newMatrix, i);
       if(maxSubMatrix < maxDimention ){
          maxSubMatrix  = maxDimention ;
         }
     }
    return maxSubMatrix;


}

private static int calcHighestDimentionBySmallestItem(int[][] matrix, int col) {

    int totalMaxDimention =0;

    for (int j = 0; j < matrix.length; j++) {
        int maxDimention = matrix[j][col];
        int numItems = 0;
        int min = matrix[j][col];
        int dimention = 0;

        for (int i = j; i < matrix.length; i++) {
            int val = matrix[i][col];
            if (val != 0) {
                if (val < min) {
                    min = val;
                }
                numItems++;
                dimention = numItems*min;
                if(dimention>maxDimention){
                    maxDimention = dimention;
                }

            } else {  //case val == 0
                numItems = 0;
                min = 0;

            }
        }
        if(totalMaxDimention < maxDimention){
            totalMaxDimention = maxDimention;
        }

    }
    return totalMaxDimention;
}

Answer 4

Решение линейно по количеству записей, а не по количеству строк или столбцов.