합계가 0 인 가장 큰 직사각형 부분 행렬


난이도 하드
자주 묻는 질문 아마존 CodeNation Directi Expedia 페이스북 서비스 구글 IBM Microsoft 페이팔 동네 짱
배열 동적 프로그래밍 매트릭스

문제 정책

합계가 2 인 2D 배열에서 최대 크기 부분 행렬을 찾습니다. 하위 행렬은 주어진 2D 배열 내부의 XNUMXD 배열에 불과합니다. 따라서 부호있는 정수로 구성된 행렬이 있으므로 부분 행렬의 합을 계산하고 합이 XNUMX 인 최대 크기의 행렬을 찾아야합니다.

합계가 0 인 가장 큰 직사각형 부분 행렬

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

설명 : 여기에 주어진 입력에는 가능한 답이 하나뿐입니다. 최대 크기 부분 행렬이 될 크기 9 (전체 행렬)의 부분 행렬을 선택할 수 있습니다. 그래서 우리는 답으로 전체 행렬을 선택할 것입니다.

Matrix = { 100
          -100
           100 }
2

설명 : 선택할 수있는 두 가지 옵션이 있습니다. 첫 번째와 두 번째 행 또는 두 번째와 세 번째 행을 선택합니다. 둘 다 합계 = 0이됩니다.

합계가 0 인 가장 큰 직사각형 부분 행렬을 찾는 방법

순진한 접근

간단한 배열을 활용하여이 문제를 해결할 수 있습니다. 다양한 셀에 대해 각각 XNUMX 개의 인덱스를 활용할 수 있습니다. 매트릭스. 이 인덱스 중 하나는 시작 행, 시작 열, 끝 행 및 끝 열에 대한 것입니다. 솔루션을 약간 개선하기 위해 2D 접두사 합계 접근 방식을 활용할 수 있습니다. 이 방법론은 간단한 솔루션을 약간 최적화 할 수 있지만 충분하지 않습니다.

효율적인 접근

따라서 우리는 문제에서했던 것과 유사한 접근 방식을 사용할 것입니다. 최대 합이있는 부분 행렬 찾기. 이제 두 개의 열을 수정합니다. 하나는 왼쪽 열용이고 다른 하나는 오른쪽 열용입니다. 0 번째 행에서 끝 행 (n-1 번째)까지 각 행에 대해이 열 사이의 합계를 저장하기 위해 임시 배열을 만듭니다. 이제 우리는 지금까지 만난 합계에 대한 인덱스를 저장하기 위해 맵 데이터 구조를 사용할 것입니다.

이 접근 방식을 이해하기 위해 다음과 같은 1D 배열을 고려할 수 있습니다. 접두사 합계, 접두사 합계 배열에서 두 개의 동일한 값을 찾으면. 즉, 요소의 합이 같을 때까지 두 개의 인덱스가 있습니다. 따라서 더 높은 지수의 합에서 더 작은 지수의 합을 빼면. 우리는 더 작은 지수와 더 높은 지수 사이의 합계를 얻습니다. 두 값이 모두 같았 기 때문입니다. 우리는 sum = 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

 

자바 코드

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)

3 개의 중첩 루프가 있기 때문에 다항식 시간 복잡도는 O (N ^ XNUMX)입니다. 하나의 루프는 접두사 Sum 및 맵 기술을 사용하여 제로 합계를 찾는 데 사용됩니다.

공간 복잡성: O (N ^ 2)

2D 접두사 Sum 배열을 만들었 기 때문에. 우리는 O (N ^ 2)의 공간 복잡도를 가지고 있습니다.