Another Java Solution using HashSet


#1

public class Solution {
public int solve(ArrayList<ArrayList> A) {
int m = A.size();
if(m == 0)
return 0;
int n = A.get(0).size();
if(n == 0)
return 0;
ArrayList<ArrayList<HashSet>> dp = new ArrayList<>();
for(int i=0;i<m;i++)
dp.add(new ArrayList<HashSet>());
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
dp.get(i).add(new HashSet());
int num = 0;
for(int i=0;i<n;i++)
if(A.get(0).get(i) == 1){
dp.get(0).get(0).add(i);
}
for(int i=1;i<m;i++){
for(Integer id: dp.get(0).get(i-1))
if(A.get(i).get(id) == 1)
dp.get(0).get(i).add(id);
}
for(int i=1;i<m;i++){
for(int j=0;j<n;j++)
if(A.get(i).get(j) == 1)
dp.get(i).get(i).add(j);
for(int j=i+1;j<m;j++){
for(Integer id: dp.get(i).get(j-1))
if(A.get(j).get(id) == 1)
dp.get(i).get(j).add(id);
}
}
for(int i=0;i<m;i++)
for(int j=i;j<m;j++)
num = (int)Math.max(num, (j-i+1)*dp.get(i).get(j).size());
return num;
}
}