백준 3321 가장 큰 직사각형

https://www.acmicpc.net/problem/3321 3321번: 가장 큰 직사각형 열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열) www.acmicpc.net n개의 행 각각에 대해 그 행을 밑변으로 하는 직사각형을 확인하면 된다. 각 행에서 각 위치에 대해 위로 연속한 1의 개수를 위 행에서의 값을 참조하여 O(m)만에 update할 수 있다. 대충 아래와 같은 그림을 생각해 보면 되겠다. 이 연속한 1의 개수를 내림차순으로 정렬하면, 그 행을 밑변으로 하는 직사각형 중 가장 큰걸 쉽게 확인할 수 있다. TC의 답을 나타낸 아래 그림과 같이, 내림차순인 히스토그램에서 가장 큰 직사각형을 구하는..

원문링크 : 백준 3321 가장 큰 직사각형