텐 센트 면접 문제 (9 도) - 면적 이 가장 큰 전체 1 자 행렬

제목 주소:http://ac.jobdu.com/problem.php?pid=1497
제목 설명:
M * N 의 행렬 에서 모든 요 소 는 0 과 1 에 불과 하 다. 이 행렬 에서 면적 이 가장 큰 전 1 자 행렬 을 찾 아 냈 다. 최대 라 는 것 은 요소 1 의 개수 가 가장 많다 는 것 을 말한다.
입력:
입력 은 여러 개의 테스트 샘플 을 포함 할 수 있 습 니 다.모든 테스트 사례 에 대해 입력 한 첫 번 째 줄 은 두 개의 정수 m, n (1 < = m, n < = 1000) 이다. 입력 할 행렬 의 크기 를 나타 낸다.행렬 은 모두 m 줄 이 있 고 줄 마다 n 개의 정수 가 있 으 며 각각 0 또는 1 이 며 인접 한 두 수 사이 에 빈 칸 으로 엄 격 히 분리 된다.
출력:
모든 테스트 사례 에 대응 하여 출력 행렬 에서 면적 이 가장 큰 전체 1 자 행렬 의 요소 갯 수 입 니 다.
샘플 입력:

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

샘플 출력:

0
4

해결 방법:
1. 동적 계획 - 세 개의 상태 배열 로 현재 점 의 높이 up, 왼쪽 경계 left, 오른쪽 경계 right, max 를 각각 저장 합 니 다.value=max(max_value,up*(right-left+1)；

#include 
using namespace std;
#include 

#define N 1000

bool data[N][N];
int up[N][N];
int l_flag[N][N];
int r_flag[N][N];

int main()
{
    int m,n;
    int max_1;
    int l_num,r_num;
    while(cin>>m>>n)
    {
        for(int i=0;i>data[i][j];
        max_1=0;
        for(int i=0;i=0;j--)
            {
                if(!data[i][j])
                {
                    r_flag[i][j]=n;
                    r_num=j;
                }
                else
                {
                    if(i==0)
                        r_flag[i][j]=r_num-1;
                    else
                        r_flag[i][j]=min(r_num-1,r_flag[i-1][j]);
                }
                max_1=max(max_1,up[i][j]*(r_flag[i][j]-l_flag[i][j]+1));
            }
        }
        cout<

2. 각 점 의 왼쪽 연속 1 개 수 를 오른쪽으로 가 져 옵 니 다. 예 를 들 어 0, 1, 1, 10 - > 0, 1, 2, 0. 그리고 각 열의 최대 1 행렬 을 계산 합 니 다. 예 를 들 어:
모 열 은 1, 2, 3, 4, 20 이 고 최대 1 행렬 은 2 * 5 = 10 이 며 구체 적 인 방법 은 각 요소 에 대해 각각 위 (왼쪽) 아래로 (오른쪽) 조회 연속 이 자신의 요소 개수 보다 큰 다음 에 곱 하 는 것 이다.
이 방법 은 9 도 에서 시간 을 초과 하 였 으 나 결 과 는 옳 았 다.

#include 
using namespace std;
#include 

bool data[1000][1000];
int flag[1000][1000];

int main()
{
    int m,n;
    int max_1,value,depth;
    int x;
    while(cin>>m>>n)
    {
        for(int i=0;i>data[i][j];
                if(data[i][j])
                {
                    if(j==0)
                        flag[i][j]=1;
                    else
                        flag[i][j]=flag[i][j-1]+1;
                }
                else
                    flag[i][j]=0;
            }
        max_1=0;
        for(int j=0;j0)
                {
                    if(flag[--x][j]>=value)
                        depth+=1;
                    else
                        break;
                }
                x=i;
                while(x=value)
                        depth+=1;
                    else
                        break;
                }
                max_1=max(max_1,depth*value);
            }
        }
        cout<