Прамавугольная падматрыца з самай вялікай плошчай з аднолькавым лікам 1 і 0


Узровень складанасці Жорсткі
Часта пытаюцца ў Accenture Сапраўды Інфармацыйны край Рашэнні для манатыпіі PayPal Pinterest Synopsys Times Інтэрнэт UHG Optum
масіў Дынамічнае праграмаванне матрыца

Пастаноўка праблемы

Дадзена двайковая матрыца памерам nx m. Праблема складаецца ў тым, каб знайсці прамавугольную падматрыцу з найбольшай плошчай з аднолькавым лікам 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. Пасля мы знаходзім суму падматрыцы пры дапамозе тэхнікі 2D-прэфікса. Але нават калі гэтага будзе недастаткова.

Эфектыўны падыход

Эфектыўным падыходам будзе спачатку змяніць кожнае 0 у матрыцы на адмоўнае 1. Пасля гэтага праблема зводзіцца да пошуку самай вялікай падматрыцы, якая мае суму 0. Мы ўжо разглядалі гэтую праблему. Гэтая праблема вырашаецца з дапамогай дынамічнае праграмаванне. Замацоўваем левы і правы слупкі. Затым захоўвайце суму элементаў кожнага радка ад першага слупка да другога слупка ў часовым масіве. Затым мы робім карту, дзе падчас перамяшчэння па гэтым часовым масіве захоўваем нумары радкоў, якія адпавядаюць суме элементаў. Такім чынам, калі мы зноў сустрэнем аднолькавае значэнне сумы ў нашым часовым масіве. Мы ўпэўненыя, што калі разгледзець элементы з радка, якія ў цяперашні час захоўваюцца на карце ў параўнанні са значэннем сумы для гэтага бягучага радка, будзе мець суму 0. І калі мы змянілі 0 на -1, мы пераўтварылі з самай вялікай плошчы прастакутны суб -матрыца з роўнай колькасцю заданняў 1 і 0 для пошуку найбольшая падматрыца, якая мае суму 0 і цяпер мы з гэтым скончылі.

Код, каб знайсці прамавугольную падматрыцу з самай вялікай плошчай з аднолькавым лікам 1 і 0

Код C ++

#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

Код Java

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

Аналіз складанасці

Складанасць часу: O (N ^ 3)

Мы маем поліномную ў часе складанасць O (N ^ 3), таму што ёсць тры ўкладзеныя завес. Адзін цыкл выкарыстоўваецца для пошуку нулявой сумы з выкарыстаннем прэфікса Сума і тэхніка карты.

Касмічная складанасць: O (N ^ 2)

Так як мы зрабілі 2D-прэфікс масіва Sum. Такім чынам, прамавугольная падматрыца з самай вялікай плошчай з аднолькавым лікам задач 1 і 0 мае шматскладовую прастору. Мы маем касмічную складанасць O (N ^ 2).