2D 행렬의 최대 합계 사각형


난이도 중급
자주 묻는 질문 Accolite 아마존 팩트 셋 삼성
배열 동적 프로그래밍 매트릭스

문제 정책

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

2D 행렬의 최대 합계 사각형

{ 0      10      0
 -1       0    100
 10    -100     10 }
110

설명 : 여기에 주어진 입력에 두 가지 가능한 답이 있습니다. 첫 번째 행의 첫 번째 열에서 두 번째 행의 세 번째 열까지 크기가 2x2 인 부분 행렬을 선택하는 것과 같습니다. 그리고 두 번째 행의 세 번째 열에서 세 번째 행, 세 번째 열까지 크기가 2 × 1 인 부분 행렬을 선택할 수도 있습니다. 두 결과 모두 답과 동일한 합계 110을 제공합니다.

{ 100
  -10
  100 }
190

설명 : 여기에 주어진 입력 2D 배열입니다. 결과적으로 전체 행렬을 선택할 수 있습니다. 총 190 개를 제공하기 때문입니다.

2D 행렬에서 최대 합계 사각형을 찾는 방법

나이브 솔루션

순진한 솔루션을 사용하여 주어진 행렬에서 최대 합계 부분 행렬을 찾을 수 있습니다. 서로 다른 인덱스에 대해 각각 2 개의 중첩 루프를 사용할 수 있습니다. 따라서 하나는 시작 행 인덱스, 시작 열 인덱스, 끝 행 인덱스 및 끝 열 인덱스에 대한 것입니다. XNUMXD를 사용할 수 있습니다. 접두사 배열 접두사의 합계를 저장합니다. 이 접근 방식은 순진한 접근 방식을 약간 최적화 할 수 있지만 충분히 효율적이지 않습니다.

효율적인 솔루션

따라서 순진한 솔루션을 사용하는 대신 Kadane의 알고리즘을 사용하여이 문제를 효율적으로 해결합니다. 하지만 문제는 2D 매트릭스에서 Kadane의 알고리즘을 어떻게 적용 할 수 있는가입니다. 우리는 즉시 두 개의 열을 수정합니다. 하나는 왼쪽 열용이고 다른 하나는 오른쪽 열용입니다. 그런 다음 두 열 사이의 합계를 배열에 저장 한 다음 Kadane의 알고리즘 해당 열 사이의 최대 연속 행 합계를 찾습니다. 최대 값으로 답변을 업데이트합니다. 가능한 모든 조합에 대해이 작업을 수행 한 후 2D 매트릭스에 최대 합계 사각형이 있습니다.

2D 행렬에서 최대 합계 사각형을 찾는 코드

C ++ 코드

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

int findMaximumSubMatrix(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 maxSum = INT_MIN;
    
    // use Kadane's algorithm for finding maximum contiguous sum in 1D array
    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, curMaxSum = 0;
            int curStartRow = 0, tmpStartRow = 0, curEndRow = -1;
            
            for(int curRow=0;curRow<n;curRow++){
                curSum += tmp[curRow];
                if(curSum < 0) {
                    curSum = 0;
                    tmpStartRow = curRow+1;
                } else if(curSum > curMaxSum) {
                    curMaxSum = curSum;
                    curStartRow = tmpStartRow;
                    curEndRow = curRow;
                }
            }

            if(curEndRow == -1) {
                curMaxSum = tmp[0];
                curStartRow = 0;
                curEndRow = 0;
                for(int i=1;i<n;i++){
                    if(tmp[i] > curMaxSum){
                        curMaxSum = tmp[0];
                        curStartRow = i;
                        curEndRow = i;
                    }
                }
            }

            if(curMaxSum > maxSum){
                maxSum = curMaxSum;
                startCol = firstCol;
                endCol = secondCol;
                startRow = curStartRow;
                endRow = curEndRow;
            }
        }
    }
    cout<<"Sub-matrix with max Sum"<<endl;
    for(int i=startRow;i<=endRow;i++){
        for(int j=startCol;j<=endCol;j++){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    return maxSum;
}

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 = findMaximumSubMatrix(matrix, n, m);
        cout<<ans<<endl;
    }
}
2
3 3
1 2 3 4 5 6 7 8 -100
2 4
102 1545 87 989 -8989 -45 120 -855
Sub-matrix with max Sum
1 2 
4 5 
7 8 
27
Sub-matrix with max Sum
102 1545 87 989 
2723

자바 코드

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

class Main {
    static int findMaximumSubMatrix(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 maxSum = Integer.MIN_VALUE;;
        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, curMaxSum = 0;
                int curStartRow = 0, tmpStartRow = 0, curEndRow = -1;
                for(int curRow=0;curRow<n;curRow++){
                    curSum += tmp[curRow];
                    if(curSum < 0) {
                        curSum = 0;
                        tmpStartRow = curRow+1;
                    } else if(curSum > curMaxSum) {
                        curMaxSum = curSum;
                        curStartRow = tmpStartRow;
                        curEndRow = curRow;
                    }
                }
    
                if(curEndRow == -1) {
                    curMaxSum = tmp[0];
                    curStartRow = 0;
                    curEndRow = 0;
                    for(int i=1;i<n;i++){
                        if(tmp[i] > curMaxSum){
                            curMaxSum = tmp[0];
                            curStartRow = i;
                            curEndRow = i;
                        }
                    }
                }
    
                if(curMaxSum > maxSum){
                    maxSum = curMaxSum;
                    startCol = firstCol;
                    endCol = secondCol;
                    startRow = curStartRow;
                    endRow = curEndRow;
                }
            }
        }
        
        System.out.println("Sub-matrix with max 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 maxSum;
    }
    
    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 = findMaximumSubMatrix(matrix, n, m);
            System.out.println(ans);
        }
    }
}
2
3 3
1 2 3 4 5 6 7 8 -100
2 4
102 1545 87 989 -8989 -45 120 -855
Sub-matrix with max Sum 
1 2
4 5 
7 8 
27 
Sub-matrix with max Sum 
102 1545 87 989 
2723

복잡성 분석

시간 복잡성: O (N ^ 3)

2D 행렬 문제의 최대 합 사각형은 3 개의 중첩 루프가 있기 때문에 다항식 시간 복잡도는 O (N ^ XNUMX)입니다. XNUMX 개는 컬럼 고정 용이고 XNUMX 개는 Kadane의 알고리즘 용입니다.

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

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