プログラム・プロムナード 最大長方形の面積

下記の連載「プログラム・プロムナード」には，有益なアルゴリズムが色々と載っているので実装してみました．

プログラム・プロムナード
http://www.ipsj.or.jp/07editj/promenade/index.html

2002年4月号 最大長方形の面積(和田英一)

import java.util.*;
import java.awt.*;

public class Main{

 // 単純なループによる実装 O(n^6)
 private int count1(int[][] a){
  int res=0;
  int m=a[0].length;
  int n=a.length;
  for(int y1=0;y1<n;y1++){
   for(int x1=0;x1<m;x1++){
    // 始点-(x1, y1)
    for(int y2=y1;y2<n;y2++){
     for(int x2=x1;x2<m;x2++){
      // 終点-(x2, y2)
      int c=0;
      // (x1, y1)-(x2, y2)から構成される長方形内の1の個数を数える
      for(int j=y1;j<=y2;j++)
       for(int i=x1;i<=x2;i++)
        if(a[j][i]==1)
         c++;
      // 長方形内のマスが全て1であり
      // 長方形の大きさ(=c)が今までの最大値より大きい場合は更新
      if(c==(x2-x1+1)*(y2-y1+1))
       if(c>res)
        res=c;
     }
    }
   }
  }
  return res;
 }
 
 // 動的計画法による実装
 private int count2(int[][] a){
  int m=a[0].length;
  int n=a.length;
  int max=0;
  LinkedList<Point>[][] lists=(LinkedList<Point>[][])new LinkedList[n][m];;
  LinkedList<Point> temp=new LinkedList<Point>();

  for(int j=0;j<n;j++)
   for(int i=0;i<m;i++)
    lists[j][i]=new LinkedList<Point>();

  for(int j=0;j<n;j++){
   for(int i=0;i<m;i++){
    if(a[j][i]==0)
     continue;
    int up, left;
    for(up=0;j-up>=0&&a[j-up][i]==1;up++)
     ;
    for(left=0;i-left>=0&&a[j][i-left]==1;left++)
     ;
    // 上隣=0，左隣=0
    if((i==0||a[j][i-1]==0)&&(j==0||a[j-1][i]==0)){
     // (1, 1)
     lists[j][i].add(new Point(1, 1));
    }
    // 上隣=0，左隣=1
    else if(j==0||a[j-1][i]==0){
     // (左方に続く1の個数, 1)
     lists[j][i].add(new Point(left, 1));
    }
    // 上隣=0，左隣=1
    else if(i==0||a[j][i-1]==0){
     // (1, 上方に続く1の個数)
     lists[j][i].add(new Point(1, up));
    }
    // 上隣=1，左隣=1
    else{
     for(Point p:lists[j][i-1])
      lists[j][i].add(new Point(p.x+1, Math.min(p.y, up)));
     for(Point p:lists[j-1][i])
      lists[j][i].add(new Point(Math.min(p.x, left), p.y+1));
    }

    // 重複要素の削除
    for(Point p:lists[j][i])
     if(!temp.contains(p))
      temp.add(p);
    lists[j][i].clear();
  
    // qより大きい長方形が存在したらqをリストに追加しない
    for(Point q:temp){
     for(Point p:temp){
      if(q!=p&&q.x<=p.x&&q.y<=p.y){
       q=null;
       break;
      }
     }
     if(q!=null)
      lists[j][i].add(q);
    }
    temp.clear();

    for(Point p:lists[j][i])
     max=Math.max(max, p.x*p.y);
   }
  }
  return max;
 }
 
 public static void main(String[] args){
  int[][] a;
  a=new int[50][50];
  for(int j=0;j<a.length;j++)
   for(int i=0;i<a[0].length;i++)
    a[j][i]=(int)(Math.random()*2);
  System.out.println("1:"+new Main().count1(a));
  System.out.println("2:"+new Main().count2(a));
 }
}

マージしないでも動作するかな?と思って，マージの実装を外して検証してみましたが，リストに保存する長方形が爆発的に増えた為，メモリが足りませんでした．