Search for a command to run...
The histogram idea
A rectangle of 1s ending on row i is exactly a rectangle under the histogram whose bar heights are the counts of consecutive 1s ending at row i. So build those heights row by row and run the largest-rectangle-in-histogram routine on each.
Histogram per Row
1function largestRectangleArea(heights) {2 const st = [];3 let maxArea = 0;4 const n = heights.length;5 for (let i = 0; i < n; i++) {6 while (st.length && heights[st[st.length - 1]] >= heights[i]) {7 const h = heights[st.pop()];8 const left = st.length ? st[st.length - 1] : -1;9 maxArea = Math.max(maxArea, h * (i - left - 1));10 }11 st.push(i);12 }13 while (st.length) {14 const h = heights[st.pop()];15 const left = st.length ? st[st.length - 1] : -1;16 maxArea = Math.max(maxArea, h * (n - left - 1));17 }18 return maxArea;19}20 21function maximalAreaOfSubMatrixOfAll1(matrix) {22 const n = matrix.length, m = matrix[0].length;23 const heights = new Array(m).fill(0);//rows: 4cols: 5maxArea: 024 let maxArea = 0;25 for (let i = 0; i < n; i++) {26 for (let j = 0; j < m; j++) {27 if (matrix[i][j] === 0) heights[j] = 0;28 else heights[j]++;29 }30 maxArea = Math.max(maxArea, largestRectangleArea(heights));31 }32 return maxArea;33}