Суммасы 0 болгон эң чоң төрт бурчтуу суб-матрица


Кыйынчылык деңгээли катуу
Көп суралган Amazon CodeNation Directi Expedia Facebook Гугл IBM Microsoft PayPal Uber
согуштук тизме Динамикалык программалоо Matrix

Маселени билдирүү

Суммасы нөлгө барабар болгон 2D массивдеги эң чоң өлчөмдөгү суб-матрицаны табыңыз. Sub-matrix - бул берилген 2D массивдин ичиндеги 2D массивден башка эч нерсе эмес. Демек, сизде кол коюлган бүтүн сандардын матрицасы бар, суб-матрицалардын суммасын эсептеп, суммасы нөлгө барабар болгон эң чоң өлчөмдөгү матрицаны табышыңыз керек.

мисал

Суммасы 0 болгон эң чоң төрт бурчтуу суб-матрица

Matrix = { 0      10      0
         -20      10    100
          10    -100    -10 }
9

Түшүндүрмө: Бул жерде берилген бир гана жооп бар. Биз эң чоң көлөмдөгү суб-матрица боло турган 9 өлчөмдөгү (бүтүндөй матрица) суб-матрицаны тандай алабыз. Ошентип, жооп катары матрицаны толугу менен тандайбыз.

Matrix = { 100
          -100
           100 }
2

Түшүндүрмө: Тандоонун эки жолу бар. Же сиз биринчи жана экинчи катарды же экинчи жана үчүнчү катарды тандайсыз. Алардын экөө тең = 0 суммасына алып келет.

Суммасы 0 болгон эң чоң төрт бурчтуу суб-матрицаны табуу ыкмасы

Naive Appocach

Бул маселени жөнөкөй тартипти колдонуу менен чечсек болот. Биз ар кандай клеткалар үчүн төрт индексти колдоно алабыз Булакта. Бул көрсөткүчтөрдүн ичинен баштапкы катар, башталгыч тилке, акыркы сап жана акыркы тилке болот. Чечимибизди бир аз өркүндөтүү үчүн 2D префикс суммасы ыкмасын колдонсок болот. Бул методика биздин жөнөкөй чечимди бир аз оптималдаштыра алат, бирок жетишсиз болот.

Натыйжалуу мамиле

Ошентип, биз көйгөйдү чечкендей эле ыкманы колдонобуз Максималдуу суммасы бар суб-матрицаны тап. Эми эки тилкени оңдойбуз, бирин сол колоннага, экинчисин оң тилке. Бул тилкелердин ортосундагы суммаларды 0-катардан баштап, акыркы сапка (n-1) чейин ар бир катар үчүн сактоо үчүн, биз убактылуу массив түзөбүз. Эми, биз ушул убакка чейин кездешкен суммалардын көрсөткүчтөрүн сактоо үчүн, картанын маалымат структурасын колдонобуз.

Ушул ыкманы оңдоо үчүн, сиз 1D массивин карасаңыз болот префикстин суммасы, жана префикстин суммасы массивинен эки бирдей маанини тапсак. Демек, бизде эки индекс бар, ага чейин элементтердин суммасы бирдей болот. Демек, жогорку индекстеги суммадан кичирээк көрсөткүчтөгү сумманы алып салсак. Биз кичинекей индекс менен жогорку индекстин ортосундагы сумманы алабыз. Ошол баалуулуктардын экөө тең бирдей болгондуктан. Бизге сумма = 0 калды. Ушул жерде эмне кылып жатабыз.

Суммасы 0 болгон эң чоң төрт бурчтуу суб-матрицаны табуу коду

C ++ коду

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

int findMaximumSubMatrixWithZeroSum(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 zero sum"<<endl;
        return 0;
    }
    cout<<"Sub-matrix with zero Sum"<<endl;
    for(int i=startRow;i<=endRow;i++){
        for(int j=startCol;j<=endCol;j++){
            cout<<matrix[i][j]<<" ";
        }
        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];
        }
        int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
        if(ans != 0)
        cout<<ans<<endl;
    }
}

 

2
4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0 -9
 1  8  8   4

4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0  9
 1  8  8   4

Largest Sub-matrix with zero Sum 
5 9 8 7 
-9 -5 -4 -2 
0 0 0 -9 
12
Largest Sub-matrix with zero Sum 
5 9 
-9 -5 
0 0 
6

 

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int findMaximumSubMatrixWithZeroSum(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 zero sum");
            return 0;
        }
        System.out.println("Largest Sub-matrix with zero Sum");
        for(int i=startRow;i<=endRow;i++){
            for(int j=startCol;j<=endCol;j++){
                System.out.print(matrix[i][j]+" ");
            }
            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();
            }
            int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
            if(ans != 0)
            System.out.println(ans);
        }
    }
}
2
4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0 -9
 1  8  8   4

4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0  9
 1  8  8   4

Largest Sub-matrix with zero Sum 
5 9 8 7 
-9 -5 -4 -2 
0 0 0 -9 
12
Largest Sub-matrix with zero Sum 
5 9 
-9 -5 
0 0 
6

 

Комплекстик анализ

Убакыт татаалдыгы: O (N ^ 3)

Бизде O (N ^ 3) полиномдук убакыт татаалдыгы бар, анткени үч уя салынган цикл бар. Бир цикл префикстин суммасы жана карта ыкмасы менен нөл суммасын табуу үчүн колдонулат.

Космостун татаалдыгы: O (N ^ 2)

2D префикси суммасы массивин жасагандыктан. Бизде O (N ^ 2) космостук татаалдыгы бар.