Careercup - Facebook面试题 - 6299074475065344

Given a matrix with 's and 0's, a rectangle can be made with 's. What is the maximum area of the rectangle. In this test case the result needs to be . How: If you see above the 's are used from the first two columns and last four rows making the area or count of 1's to be .

// http://www.careercup.com/question?id=6299074475065344
#include <vector>
using namespace std; class Solution {
public:
int maxRectangleWithAllOnes(vector<vector<int> > &v) {
n = (int)v.size();
if (n == ) {
return ;
}
m = (int)v[].size();
if (m == ) {
return ;
} int i, j;
int res, max_res; histogram.resize(m);
left.resize(m);
right.resize(m);
fill_n(histogram.begin(), m, );
max_res = ;
for (i = ; i < n; ++i) {
for (j = ; j < m; ++j) {
histogram[j] = v[i][j] ? histogram[j] + v[i][j]: ;
res = maxRectangleInHistogram(histogram);
max_res = res > max_res ? res : max_res;
}
} histogram.clear();
left.clear();
right.clear(); return max_res;
};
private:
vector<int> histogram;
vector<int> left;
vector<int> right;
int n, m; int maxRectangleInHistogram(vector<int> &histogram) {
int i;
int j; left[] = ;
for (i = ; i <= n - ; ++i) {
j = i - ;
left[i] = i;
while (j >= && histogram[i] <= histogram[j]) {
left[i] = left[j];
j = left[j] - ;
}
} right[n - ] = n - ;
for (i = n - ; i >= ; --i) {
j = i + ;
right[i] = i;
while (j <= n - && histogram[i] <= histogram[j]) {
right[i] = right[j];
j = right[j] + ;
}
} int max_res, res;
max_res = ;
for (i = ; i < n; ++i) {
res = histogram[i] * (right[i] - left[i] + );
max_res = res > max_res ? res : max_res;
} return max_res;
};
}; int main()
{
int n, m;
int i, j;
vector<vector<int> > v;
Solution sol; while (scanf("%d%d", &n, &m) == && (n > && m > )) {
v.resize(n);
for (i = ; i < n; ++i) {
v[i].resize(m);
}
for (i = ; i < n; ++i) {
for (j = ; j < m; ++j) {
scanf("%d", &v[i][j]);
}
}
printf("%d\n", sol.maxRectangleWithAllOnes(v)); for (i = ; i < n; ++i) {
v[i].clear();
}
v.clear();
} return ;
}