Given a binary matrix. Find the maximum area of a rectangle formed only of 1s in the given matrix.

Given a binary matrix. Find the maximum area of a rectangle formed only of 1s in the given matrix.

Algorithm 

// { Driver Code Starts
#include <bits/stdc++.h>

using namespace std;#
define MAX 1000

int maxArea(int M[MAX][MAX], int n, int m);
int main() {
    int T;
    cin >> T;

    int M[MAX][MAX];

    while (T--) {
        int n, m;
        cin >> n >> m;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> M[i][j];
            }
        }
        cout << maxArea(M, n, m) << endl;
    }
}
// } Driver Code Ends


/*You are required to complete this method*/
int maxArea(int M[MAX][MAX], int n, int m) {
    // Your code here
    int a[m], ar = 0, mx = 0;
    memset(a, 0, sizeof(a));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {

            if (M[i][j] == 0) {
                a[j] = 0;
            } else {
                a[j] += M[i][j];
            }
        }
        stack < int > s;
        int l, top, k;
        for (k = 0; k < m;) {
            if (s.empty()) {
                l = k;
                s.push(k++);
            } else if (a[s.top()] <= a[k]) {
                s.push(k++);
            } else if (a[s.top()] > a[k]) {
                top = s.top();
                s.pop();
                if (s.empty()) {
                    ar = a[top] * k;
                    mx = max(ar, mx);
                } else {
                    ar = a[top] * (k - s.top() - 1);
                    mx = max(ar, mx);
                }
            }
        }

        while (!s.empty()) {
            top = s.top();
            s.pop();
            if (!s.empty()) {
                ar = a[top] * (k - s.top() - 1);
                mx = max(ar, mx);
            }
        }

        if (s.empty()) {
            ar = a[top] * k;
            mx = max(ar, mx);
        }

    }
    return mx;
}