すべて同じ番号の最大長方形

Question

与えられた配列n×m。その中に同じ番号がすべて含まれている最大の矩形を見つける必要があります。
例：ここ
1 2 2 5
1 2 2 4
2 2 2 3
答えは質問がおよそ最大の広場に言わせれば、私はこの問題を解決することができます6.

でなければなりません。ここに私のアプローチがある -

for(int i=0; i<n; i++) for(int j=0; j<m; j++) { 
    if(!i && !j) dp[i][j] = 1; 
    else if(a[i][j] == a[i-1][j-1] && 
     a[i][j] == a[i-1][j] && 
     a[i][j] == a[i][j-1]) 
      dp[i][j] = min({dp[i-1][j-1], dp[i][j-1], dp[i-1][j]}) + 1; 
    else dp[i][j] = 1; 
} 

すると答えはDPテーブルの最大数でなければなりません。どのようにこれを変更して最大の長方形を得ることができますか？

Answer 1

rectの長さと幅を格納するには、3次元配列（dp[INT_MAX][INT_MAX][2]）が必要です。

else if(a[i][j] == a[i-1][j-1] && 
    a[i][j] == a[i-1][j] && 
    a[i][j] == a[i][j-1]) 
{  
     //for length along j 
     dp[i][j][0]=min(dp[i][j][0]+1,dp[i-1][j-1][0]+1,dp[i][j][0]); 

     //for length of rectangle along i 
     dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][1]+1,dp[i][j][1]); 
} 

レストWith- replacing-

else if(a[i][j] == a[i-1][j-1] && 
    a[i][j] == a[i-1][j] && 
    a[i][j] == a[i][j-1]) 
     dp[i][j] = min({dp[i-1][j-1], dp[i][j-1], dp[i-1][j]}) + 1; 

により矩形が単一裏打ちされた場合に、他の単純用いて解くことができる些細な場合です。