[LeetCode] Maximal Rectangle

Problem:
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Solution:O(m*n)

public class Solution {
  public int maximalRectangle(char[][] matrix) {
    if(matrix.length==0) 
        return 0;

    int maxSum=0;
    int[] hist = new int[matrix.length];

    for(int j=0;j<matrix[0].length;j++){
        for(int i=0;i<matrix.length;i++){
            if(matrix[i][j]=='1')
                hist[i]++;   
            else    
                hist[i] = 0;
        }
        maxSum = Math.max( maxSumRectHist(hist), maxSum);
    }
    return maxSum;
  }
    
  public int maxSumRectHist(int[] hist){
    int maxSum=0;
    int prev=-1;

    for(int i=0;i<hist.length;i++){
        if(hist[i] == 0)
            continue;
        
        int curmax = hist[i];
        int min = curmax; 
        for(int t= i-1; t>=0; t--){
            if(hist[t] == 0){
                break;
            }else{
                min = Math.min(min,hist[t]);
                curmax = Math.max(curmax, min*(i-t+1));
            }
        }
        maxSum = Math.max( curmax, maxSum);
    }
    return maxSum;
  }
}

Key concept: Use smart DP and reuse the same array.