Правоугаона под-матрица највеће површине са једнаким бројем 1 и 0  


Ниво тешкоће Тежак
Често питани у Аццентуре Заиста Инфо Едге Монотипска решења ПаиПал Пинтерест Синопсис Тимес Интернет УХГ Оптум
Ред Динамичко програмирање матрица

Изјава о проблему  

Дата је бинарна матрица величине нк м. Проблем је пронаћи правоугаону под-матрицу највеће површине са једнаким бројем 1 и 0.

Пример  

Пин

Dimensions = 4 x 4
Matrix:
1 1 1 1
0 1 0 1
1 0 1 0
1 0 0 0
12

Објашњење: Ако узмемо у обзир подматрицу са угловима (0,1), (0,3), (3,1) и (3,3). Ова под-матрица чини највећи правоугаони под-матикс који има једнак број 0 и 1.

Dimesnions = 2 x 4
Matrix:
0 0 1
0 1 1
6

Објашњење: Будући да је почетна матрица имала једнак број 0 и 1, тада ће иницијална матрица бити наш одговор. То је овде случај.

Приступ  

Наивни приступ

Најлакше што можемо учинити је разматрање по четири показивача за индексе под-матрице у сва четири правца. Када смо поправили под-матрицу, можемо да избројимо број 0 и 1. Али ово није ефикасан приступ и сигурно ће премашити временска ограничења. Можемо мало оптимизовати проблем ако сваку 0 променимо са -1. После тога проналазимо зброј под-матрице користећи технику 2Д префикса. Али иако то неће бити довољно.

Ефикасан приступ

Ефикасан приступ биће прво мењање сваке 0 у матрици са негативном 1. После тога проблем се своди на проналажење највеће под-матрице која има збир 0. Овај проблем смо већ покрили. Овај проблем се решава помоћу динамичко програмирање. Поправљамо леву и десну колону. Затим у привремени низ сместите збир елемената сваког реда од прве колоне до друге колоне. Затим правимо мапу, где складиштимо бројеве редова који одговарају зброју елемената док обилазимо овај привремени низ. Дакле, ако поново нађемо исту вредност збира у нашем привременом низу. Сигурни смо да ће, ако узмемо у обзир елементе из реда, који се тренутно чувају на мапи у односу на вредност збира у овом тренутном реду, имати зброј 0. А када смо променили 0 на -1, претворили смо из правоугаоне подправке највеће површине -матрица са једнаким бројем 1 и 0 проблема за проналажење највећа под-матрица која има збир 0 и сад смо с тим завршили.

Види такође
Биномни коефицијент

Код за проналажење правоугаоне под-матрице највећег подручја са једнаким бројем 1 и 0  

Ц ++ код

#include<bits/stdc++.h>
using namespace std;

int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (vector<vector<int>> matrix, int n, int m){
  
    // stores the prefixSum of rows
    vector<vector<int>> prefixSum(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            prefixSum[i][j] = matrix[i][j];
    }
    
    // calculation prefix sum for each row
    for(int i=0;i<n;i++){
        for(int j=1;j<m;j++)
            prefixSum[i][j] += prefixSum[i][j-1];
    }
    
    // store indices of submatrix with maximum sum
    int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
    int maxSize = 0;
    // use a map to first store the row for sum if it was not present earlier
    // else we calculate the result regarding the particular sum
    for(int firstCol=0;firstCol<m;firstCol++){
        for(int secondCol=firstCol;secondCol<m;secondCol++){
            int tmp[n]; // stores the sum between two columns for each row
            for(int row=0;row<n;row++)
                tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
            int curSum = 0;
            unordered_map<int,int> rowSumMap;
            rowSumMap[0] = -1;
            for(int curRow=0;curRow<n;curRow++){
                curSum += tmp[curRow];
                if(rowSumMap.count(curSum)) {
                    int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap[curSum]);
                    if(subMatrixSize > maxSize){
                        maxSize = subMatrixSize;
                        startCol = firstCol;
                        endCol = secondCol;
                        startRow = rowSumMap[curSum] + 1;
                        endRow = curRow;
                    }
                } else {
                    rowSumMap[curSum] = curRow;
                }
            }
        }
    }
    
    if(maxSize == 0){
        cout<<"There exists no sub-matrix with equal numbers of 0s and 1s"<<endl;
        return 0;
    }
    cout<<"Largest Sub-matrix with equal number of 1s and 0s"<<endl;
    for(int i=startRow;i<=endRow;i++){
        for(int j=startCol;j<=endCol;j++){
            cout<<(matrix[i][j]>0 ? 1 :  0)<<" ";
        }
        cout<<endl;
    }
    return maxSize;
}

int main(){
  
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        vector<vector<int>> matrix(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>matrix[i][j];
                matrix[i][j] = matrix[i][j] ? 1 : -1;
            }
        }
        int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s(matrix, n, m);
        if(ans != 0)
        cout<<ans<<endl;
    }
}
1
4 4
1 1 1 1
0 1 0 1
1 0 1 0 
1 0 0 0
Largest Sub-matrix with equal number of 1s and 0s
1 1 1
1 0 1
0 1 0
0 0 0
12

Јава Цоде

import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
    static int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (int[][] matrix, int n, int m){
        // stores the prefixSum of rows
        int[][] prefixSum = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                prefixSum[i][j] = matrix[i][j];
        }
    
        // calculation prefix sum for each row
        for(int i=0;i<n;i++){
            for(int j=1;j<m;j++)
                prefixSum[i][j] += prefixSum[i][j-1];
        }
    
        int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
        int maxSize = 0;
        for(int firstCol=0;firstCol<m;firstCol++){
            for(int secondCol=firstCol;secondCol<m;secondCol++){
                int tmp[] = new int[n]; // stores the sum between two columns for each row
                for(int row=0;row<n;row++)
                    tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
                
                int curSum = 0;
                HashMap<Integer, Integer> rowSumMap = new HashMap<Integer, Integer>();
                rowSumMap.put(0,-1);
                for(int curRow=0;curRow<n;curRow++){
                    curSum += tmp[curRow];
                    if(rowSumMap.containsKey(curSum)) {
                        int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap.get(curSum));
                        if(subMatrixSize > maxSize){
                            maxSize = subMatrixSize;
                            startCol = firstCol;
                            endCol = secondCol;
                            startRow = rowSumMap.get(curSum) + 1;
                            endRow = curRow;
                        }
                    } else {
                        rowSumMap.put(curSum,curRow);
                    }
                }
            }
        }
        
        if(maxSize == 0){
            System.out.println("There exists no sub-matrix with equal number of 1s and 0s");
            return 0;
        }
        System.out.println("Largest Rectangular Sub-matrix with equal number of 1s and 0s");
        for(int i=startRow;i<=endRow;i++){
            for(int j=startCol;j<=endCol;j++){
                System.out.print((matrix[i][j]>0) ? "1 " : "0 ");
            }
            System.out.println();
        }
        return maxSize;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int matrix[][] = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    matrix[i][j] = sc.nextInt();
                    matrix[i][j] = matrix[i][j]>0 ? 1 : -1;
                }
            }
            int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (matrix, n, m);
            if(ans != 0)
            System.out.println(ans);
        }
    }
}
1
4 4
1 1 1 1
0 1 0 1
1 0 1 0
1 0 0 0
Largest Rectangular Sub-matrix with equal number of 1s and 0s
1 1 1
1 0 1
0 1 0
0 0 0
12

Анализа сложености  

Сложеност времена: О (Н ^ 3)

Имамо полиномно-временску сложеност О (Н ^ 3) јер постоје три угнежђена петље. Једна петља се користи за проналажење нулте суме помоћу технике префикса Сум и мап.

Види такође
Проверите формирање низа кроз решење за повезивање Леетцоде-а

Сложеност простора: О (Н ^ 2)

Пошто смо направили 2Д префикс Сум низ. Дакле, правоугаона под-матрица највећег подручја са једнаким бројем проблема 1 и 0 има сложеност полиномског простора. Имамо сложеност простора од О (Н ^ 2).