參考文章

• 算法1
• 算法2

懸線法

懸線法——解決最大子矩陣問題

最大子矩陣問題

在一個給定的矩形中有一些障礙點，找出內部不包含障礙點的、輪廓與整個矩形平行或重合的最大子矩形。

定義

1 懸線：懸線是一條以矩陣上邊界或障礙點爲頂點的不通過障礙點的豎線
2 極大子矩形：內部不包含障礙點，四條邊或貼合邊界或存在障礙點（沒法再經過平移邊擴大）的矩形html

方法概述

因爲最大子矩陣必定是某一個極大子矩陣，因此枚舉極大子矩陣就能夠找出最大子矩陣。可是極大子矩陣並不能被直接找到，因而該題就被轉化成爲了如何枚舉極大子矩陣。具體如何使用懸線法有如下兩種狀況。ios

點疏

時間複雜度O（S^2）c++

• 既然要枚舉矩陣，咱們能夠經過枚舉其邊界來確認矩陣，可是粗略一算髮現時間複雜度爆炸，思考其緣由，發現咱們在枚舉邊界的時候產生了大量的內部存在障礙點的子矩形，即便屬於符合題目要求的子矩形，也有可能不是極大子矩形，那麼如何利用邊枚舉極大有效子矩形呢？
• 由於極大子矩陣的邊界必需要存在障礙點或矩形邊界，因此這裏先將障礙點排序，而後從左到右枚舉障礙點，當枚舉到x號點，x號點便做爲極大子矩形的左邊界，上下邊界爲原矩形的上下邊界，再加一層循環掃描x點後的每一個點，統計以次點爲右邊界，當前上下邊界爲上下邊界的極大子矩形面積，而後更新上下邊界，再找下一個點，一直枚舉便可。
• 更新上下邊界時，若是當前點在x號點的下方則須要更新下邊界，在上方則須要更新上邊界，在中間要分類討論。
• 僅這樣作一遍會有遺漏，如邊界和矩形邊界重合的狀況，解決方法是在預處理的時候加上邊界的四個角做爲障礙點，從右到左再掃一遍，搞定

點密

時間複雜度O（n*m）web

• 這裏用枚舉矩陣內全部點的方法，由懸線的定義可知，每個點做爲懸線的下端點時（障礙點也能夠作懸線的下端點）都對應了一條且僅有一條懸線，將這條懸線向左邊、右邊平移，直到遇到障礙點或邊界，必能掃描出一個矩形。而這全部矩形的集合必然包涵了極大子矩陣的集合，同時包含了最大子矩陣。算法

• 假設咱們計算子矩陣的大小時間複雜度爲O（1），那麼這個算法的時間複雜度就取決於完整矩陣的邊長O（m*n），如今問題再次轉化，轉化爲如何最快地確認當前掃描的子矩陣的大小app

• 當咱們發現並不可以單純地O（1）計算時，考慮狀態轉移，發現若是當前點正上方的一個點不是障礙點，那麼懸線長度爲上一條加一，不然爲1svg

• 而左右可以到達的最大位置經過比較原位置和更新高度後新的一行的障礙點來修改，這裏經過以前的理論提出定義和公式spa

• 定義code

• $Height_{(i,j)}$ ：以（i，j）爲下端點的懸線的高
  $Left_{(i,j)}$ ：懸線（i，j）能到達的左邊界
  $Right_{(i,j)}$：懸線（i，j）能到達的左邊界xml

• 初始化
  $Height_{(i,j)} =1$
  $Left_{(i,j)} =j$
  $Right_{(i,j)} =j$
  左右邊界任然須要按照題目要求初始化

• 遞推式
  $Height_{(i,j)} =Height_{(i-1,j)}+1$
  $Left_{(i,j)} =max(Left_{i-1,j},Left_{(i,j)})$
  $Right_{(i,j)} =min(Right_{i-1,j},Right_{(i,j)})$

• 而後就能夠經過狀態轉移計算面積了，搞定

例題

算法1

[vijos1055] 奶牛浴場
AC代碼（醜）：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <map>
#include <stack>
#include <cmath>
#define LL long long 
using namespace std; 

struct point
{
	int x,y;
} p[5005];

bool cmp(point a,point b)
{
	return a.x<b.x;
}

bool cmp3(point a,point b)
{
	return a.y<b.y;
}

int main()
{	
	int l,w,n,s=0;
	scanf("%d%d%d",&l,&w,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&p[i].y,&p[i].x);
		if(p[i].y<=0)	p[i].y=0;
		if(p[i].x<=0)	p[i].x=0;
		if(p[i].y>l)	p[i].y=l;
		if(p[i].x>w)	p[i].x=w;
	}
	p[n+1].y=0,p[n+1].x=1,n++;
	p[n+1].y=l,p[n+1].x=1,n++;
	p[n+1].y=0,p[n+1].x=w,n++;
	p[n+1].y=l,p[n+1].x=w,n++;
	sort(p+1,p+n+1,cmp3); 
	for(int i=2;i<=n;i++)
		s=max(s,(p[i].y-p[i-1].y)*l);
	sort(p+1,p+n+1,cmp); 
	for(int i=1;i<=n-1;i++)
	{
		int h1=0,h2=l;                     
		for(int j=i+1;j<=n;j++)
		{
			if(p[i].x==p[j].x)
				continue;
			s=max(s,(h2-h1)*(p[j].x-p[i].x));
			if(p[j].y<h2&&p[j].y>h1)
			{
				if(p[j].y<p[i].y)
					h1=p[j].y;
				else if(p[j].y>p[i].y)
					h2=p[j].y;
				else
				{
					h1=p[j].y;
				}
			}
		}
	}	
	for(int i=1;i<=n-1;i++)
	{
		int h1=0,h2=l;                     
		for(int j=i+1;j<=n;j++)
		{
			if(p[i].x==p[j].x)
				continue;
			s=max(s,(h2-h1)*(p[j].x-p[i].x));
			if(p[j].y<h2&&p[j].y>h1)
			{
				if(p[j].y<p[i].y)
					h1=p[j].y;
				else if(p[j].y>p[i].y)
					h2=p[j].y;
				else
				{
					h2=p[j].y;
				}
			}
		}
	}	
	cout<<s<<endl;
}

算法2

P1169 [ZJOI2007] 棋盤製做
AC代碼(初始化寫錯查了好久，真蠢)：

#include<bits/stdc++.h>
using namespace std;

int mp[2005][2005];
int lft[2005][2005],rit[2005][2005],height[2005][2005];

int main()
{    
    int n,m,ans1=0,ans2=0; 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    	{
    		scanf("%d",&mp[i][j]);
    		lft[i][j]=j,rit[i][j]=j;
    		height[i][j]=1;
		}
	for(int i=1;i<=n;i++)
		for(int j=2;j<=m;j++)
			if(mp[i][j]!=mp[i][j-1])
				lft[i][j]=lft[i][j-1];
	for(int i=1;i<=n;i++)
		for(int j=m-1;j>=1;j--)
			if(mp[i][j]!=mp[i][j+1])
				rit[i][j]=rit[i][j+1];
	for(int i=2;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(mp[i][j]!=mp[i-1][j])
			{
				lft[i][j]=max(lft[i][j],lft[i-1][j]);
				rit[i][j]=min(rit[i][j],rit[i-1][j]);
				height[i][j]=height[i-1][j]+1;
			} 
			int h=height[i][j];
	 		int l=rit[i][j]-lft[i][j]+1;
			ans1=max(ans1,min(l,h)*min(l,h));
			ans2=max(ans2,l*h);	
		}	
	cout<<ans1<<"\n"<<ans2<<endl; 
}