Maximal Color Rectangle

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N x N 격자의 각 칸에 색 ID가 주어질 때, 모든 칸이 같은 색인 가장 큰 축에 나란한 직사각형의 넓이를 구한다.

난이도: 어려움10점 중 8점
유형: 스택, 누적 합, 동적 계획법
정답자: 아직 제출이 없습니다

문제

You are given an $N \times N$ grid $A$ where each cell contains an integer color ID $A\_{ij}$ . Your task is to find the largest axis-aligned rectangle whose cells all have the same color, and report its area.

In this figure, the maximal area satisfying the problem’s conditions is $6$ . Note that rectangle must be axis-aligned and contiguous in rows and columns.

입력

The first line contains a single integer $N$ , representing the size of the grid $A$ . $(1 \leq N \leq 2\\,000)$

The next $N$ lines each contain $N$ integers, integer denotes the color ID $A\_{ij}$ . $(-1\\,000\\,000 \leq A\_{ij} \leq 1\\,000\\,000)$

출력

Print a single integer: the maximal area satisfying the problem’s conditions.

예제3

예제 1
입력
```
4
1 0 0 0
1 0 1 0
1 1 0 0
0 1 1 0
```
예상 출력
```
4
```
예제 2
입력
```
4
1 2 2 2
1 2 2 2
1 2 2 2
3 3 0 -1
```
예상 출력
```
9
```

예제 3

입력

6
1 1 2 2 2 4
1 1 1 2 2 4
3 1 1 2 2 2
3 3 3 3 3 2
4 4 4 4 4 5
5 5 5 5 1 1

예상 출력