أكبر مصفوفة فرعية مستطيلة مجموعها 0


مستوى الصعوبة الثابت
كثيرا ما يطلب في أمازون CodeNation Directi اكسبيديا Facebook جوجل IBM Microsoft Paypal اوبر
مجموعة البرمجة الديناميكية مصفوفة

المشكلة بيان

أوجد الحجم الأقصى لمصفوفة فرعية في مصفوفة ثنائية الأبعاد مجموعها صفر. المصفوفة الفرعية ليست سوى مصفوفة ثنائية الأبعاد داخل المصفوفة ثنائية الأبعاد المحددة. إذن ، لديك مصفوفة من الأعداد الصحيحة ذات الإشارة ، تحتاج إلى حساب مجموع المصفوفات الفرعية وإيجاد المصفوفة ذات الحجم الأقصى التي يكون مجموعها صفرًا.

مثال

أكبر مصفوفة فرعية مستطيلة مجموعها 0

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

التفسير: هنا ، في هذا الإدخال المعطى لدينا إجابة واحدة فقط ممكنة. يمكننا اختيار مصفوفة فرعية بحجم 9 (مصفوفة كاملة) والتي ستكون الحجم الأقصى لمصفوفة فرعية. لذا ، سنختار المصفوفة بأكملها كإجابة.

Matrix = { 100
          -100
           100 }
2

شرح: هناك خياران للاختيار من بينها. إما أن تختار الصف الأول والثاني أو الصف الثاني والثالث. كلاهما سينتج عنه مجموع = 0.

اقترب من إيجاد أكبر مصفوفة فرعية مستطيلة ومجموعها 0

نهج ساذج

يمكننا الاهتمام بهذه المشكلة من خلال استخدام ترتيب بسيط. يمكننا استخدام أربعة مؤشرات لكل منها لخلايا مختلفة من البخور. من بين هذه المؤشرات ، سيكون أحدها لصف البداية ، وعمود البداية ، وصف النهاية ، وعمود الإنهاء. يمكننا استخدام نهج مجموع البادئة ثنائية الأبعاد لتحسين حلنا بشكل طفيف. يمكن لهذه المنهجية تحسين حلنا البسيط قليلاً ولكن هذا لن يكون كافيًا.

نهج فعال

لذلك ، سوف نستخدم نهجًا مشابهًا كما فعلنا مع المشكلة أوجد مصفوفة فرعية بأقصى مجموع. سنقوم الآن بإصلاح عمودين ، أحدهما للعمود الأيسر والآخر للعمود الأيمن. لتخزين المجاميع بين هذه الأعمدة لكل صف من الصفوف بدءًا من الصف 0 وحتى الصف الأخير (n-1th) ، سننشئ مصفوفة مؤقتة. الآن ، سوف نستفيد من بنية بيانات الخريطة لتخزين فهارس المبالغ التي تمت مواجهتها حتى الآن.

فقط للتعرف على هذا النهج ، يمكنك التفكير في مجموعة 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

 

كود جافا

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) لأن هناك ثلاث حلقات متداخلة. يتم استخدام حلقة واحدة لإيجاد المجموع الصفري باستخدام تقنية البادئة Sum وتقنية الخريطة.

تعقيد الفضاء: O (N ^ 2)

منذ أن صنعنا مجموعة مجموع بادئة ثنائية الأبعاد. لدينا تعقيد فضائي لـ O (N ^ 2).