AOJ

# # Problem

https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_B

# # Explanation

This problem can be seen as a histgram max are.

# # Time complexity

$O(HW)$

# # Solution

#define MAX_H 1401
#define MAX_W 1401

Int H, W;
bool C[MAX_H][MAX_W];
Int HIST[MAX_H][MAX_W];

void input() {
cin >> H >> W;
loop(h,0,H) {
loop(w,0,W) {
cin >> C[h][w];
}
}
}

// O(N)
Int max_hist(Int hist[]) {
stack<Int> S;
Int max_ = 0, area = 0, tp = -1, width = 0;

loop (i,0,W) {
Int height = hist[i];

// Pop every bar which is higher than me and calculate area for each of them.
while (!S.empty() && hist[S.top()] > height) {
tp = S.top();S.pop();

width = S.empty() ? i : i - S.top() - 1;
area = hist[tp] * width;
if (max_ < area) max_ = area;
}

// Now bars are sorted in ascending order (greater or equal)
S.push(i);
}

Int maxWidth = W;
while (!S.empty()) {
tp = S.top();S.pop();

width = S.empty() ? maxWidth : maxWidth - S.top() - 1;
area = hist[tp] * width;
if (max_ < area) max_ = area;
}

return max_;
}

void solve() {
loop(w,0,W) {
HIST[0][w] = C[0][w] ? 0 : 1;
}

loop(w,0,W) {
loop(h,1,H) {
HIST[h][w] = C[h][w] ? 0 : HIST[h-1][w] + 1;
}
}

Int max_ = 0;
loop(h,0,H) {
max_ = max(max_, max_hist(HIST[h]));
}

cout << max_ << endl;
}

int main(void) {
input();
solve();
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!