POJ.3494 Largest Submatrix of All 1’s

1.Problem
3494 -- Largest Submatrix of All 1’s (poj.org)

2.Idea
Apply the max rectangle in histogram problem.

3.Source

 int m, n;  
 int h[2200];  
 int st[2200], L[2200], R[2200];  
 int maxRec() {  
      //L  
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R  
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (R[i] - L[i]));  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (cin >> m >> n) {  
           memset(h, 0, sizeof h);  
           int ans = 0;  
           for (int i = 0; i < n; i++) {  
                for (int j = 0; j < m; j++) {  
                     int t; scanf("%d", &t);  
                     h[j] = t ? h[j] + 1 : 0;  
                }  
                ans = max(ans, maxRec());  
           }  
           printf("%d\n", ans);  
      }  
 }