मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है, हमें दिए गए मैट्रिक्स में सभी 1 का सबसे बड़ा आयत ढूंढना है। आयत को उस मैट्रिक्स के किसी भी जोड़े के कॉलम की अदला-बदली या अदला-बदली करके बनाया जा सकता है।
तो, अगर इनपुट पसंद है
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
तो इस मामले में आउटपुट 6 होगा। कॉलम 1 को 3 से बदलकर आयत बनाया जा सकता है। आदान-प्रदान के बाद मैट्रिक्स होगा -
| 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
पंक्ति :=चटाई का आकार
-
कर्नल:=चटाई का आकार[0]
-
अस्थायी:=क्रम का एक मैट्रिक्स (पंक्ति + 1) x (कॉल + 1), और 0 से भरें
-
मैं के लिए 0 से कर्नल की सीमा में, करते हैं
-
अस्थायी [0, मैं]:=चटाई [0, मैं]
-
j के लिए 1 से पंक्ति की श्रेणी में, करें
-
अगर मैट [जे, आई] 0 के समान है, तो
-
अस्थायी [जे, आई]:=0
-
-
अन्यथा,
-
अस्थायी [जे, आई]:=अस्थायी [जे -1, आई] + 1
-
-
-
-
मैं के लिए 0 से पंक्ति की सीमा में, करते हैं
-
cnt :=आकार की एक सरणी (पंक्ति + 1), और 0 से भरा हुआ
-
j के लिए 0 से col तक, 1 की वृद्धि करें
-
सीएनटी [अस्थायी [आई, जे]]:=सीएनटी [अस्थायी [i, जे]] + 1
-
-
col_no :=0
-
जे:=पंक्ति
-
जबकि j>=0, करें
-
अगर cnt[j]> 0, तो
-
k के लिए 0 से cnt[j] की सीमा में, करें
-
अस्थायी [i, col_no] :=j
-
col_no :=col_no + 1
-
-
-
जे:=जे - 1
-
-
-
क्षेत्र_अधिकतम :=0
-
मैं के लिए 0 से पंक्ति की सीमा में, करते हैं
-
j के लिए 0 से col की सीमा में, करें
-
area_current :=(j + 1) * temp[i, j]
-
अगर area_current> area_maximum, तो
-
area_maximum :=area_current
-
-
-
-
वापसी क्षेत्र_अधिकतम
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def maxArea(mat):
row = len(mat)
col = len(mat[0])
temp = [[0 for i in range(col + 1)] for i in range(row + 1)]
for i in range(0, col):
temp[0][i] = mat[0][i]
for j in range(1, row):
if ((mat[j][i] == 0)):
temp[j][i] = 0
else:
temp[j][i] = temp[j - 1][i] + 1
for i in range(0, row):
cnt = [0 for i in range(row + 1)]
for j in range(0, col, 1):
cnt[temp[i][j]] += 1
col_no = 0
j = row
while(j >= 0):
if (cnt[j] > 0):
for k in range(0, cnt[j]):
temp[i][col_no] = j
col_no += 1
j -= 1
area_maximum = 0
for i in range(0, row):
for j in range(0, col):
area_current = (j + 1) * temp[i][j]
if (area_current > area_maximum):
area_maximum = area_current
return area_maximum
mat = [
[0, 0, 1, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 1, 1, 0]]
print("Area : ",maxArea(mat)) इनपुट
[ [1, 0, 0, 1, 0], [1, 0, 0, 1, 1], [1, 1, 0, 1, 0]]
आउटपुट
Area : 2