This repository was archived by the owner on Sep 7, 2025. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 338
Expand file tree
/
Copy pathmaxRectangle.cpp
More file actions
89 lines (64 loc) · 1.47 KB
/
maxRectangle.cpp
File metadata and controls
89 lines (64 loc) · 1.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
int largestRectangleArea(vector<int> &hist) {
stack<int> s;
int n=hist.size();
int max_area = 0;
int tp;
int area_with_top;
int i = 0;
while (i < n)
{
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
else
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
}
while (s.empty() == false)
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
int maximalRectangle(vector<vector<int> > &A) {
int i,j,k,l,n=A.size(),m=A[0].size(),maxi=0;
vector<int> vec(m,0);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(A[i][j]==0)
vec[j]=0;
else
vec[j]+=1;
}
maxi=max(maxi,largestRectangleArea(vec));
}
return maxi;
}
int main(){
int n,i,j,m,x;
vector<vector<int> > vec;
vector<int> arr;
cin>>n>>m;
for(i=0;i<n;i++){
arr.clear();
for(j=0;j<m;j++)
{
cin>>x;
arr.push_back(x);
}
vec.push_back(arr);
}
cout<<maximalRectangle(vec);
}