금광 문제는 가중치를 가지는 정점들이 평면상에 주어졌을 때 임의의 직사각형을 정하여 그 안에 속한 점들의 가중치를 최대화하는 문제이다. 답에 해당하는 직사각형 R을 최소화하면 각 변에는 적어도 하나의 점이 위치하게 된다. 즉, 답이 되는 최소 직사각형의 네 변은 광 산의 위치로 주어지는 x,y좌표를 이용해 구성할 수 있다.입력된 광산 위치의 x좌표 (N개)와 y좌표 (N개)를 조합하면 답이 되는 직사각형의 꼭지점 후보를 N×N 개 만들 수 있다. 이 꼭지점 후보 중 두 점을 꼭지점(왼쪽 위 꼭지점-오른쪽 아래 꼭지점)으로 뽑아 직사각형을 구성하면 O(N^4)개의 직사각형 후보가 나온다. 각 직사각형 후보 (X1,Y1) - (X2-Y2)에 속하는 정점의 가중치 합을 구하여 답을 찾을 수 있다. (0,0) - (X,Y) 직사각형 속 점들의 가중치 합 Sx,y�뭏� O(N^2)에 미리 계산해 놓으면, 직사각형 (X1,Y1) - (X2,Y2)에 속하는 정점의 가중치 합은 Sx2,y2 - Sx1-1,y2 - Sx2,y1-1 + Sx1-1,y1-1 가 되므로 O(1) 에 알 수 있다. 부분문제 1의 경우 이 방법으로 O(N^4)에 해결 가능하다.
위의 방법에 최대 연속 부분합을 적용하여 O(N^3)으로 개선할 수 있다. 우선 정점들을 X 축을 기준으로 정렬하고, 직사각형의 위, 아래 변이 되는 축 2개를 선택한다. 그 속에 있는 정점들을 X 축 기준으로 정렬한 순서대로 최대 연속 부분합을 계산하면 O(N)에 주어진 위, 아래 변에 대해 정점의 가중치 합이 최대가 되는 직사각형의 양 옆 변을 구할 수 있다. 이 방법을 통해 부분문제 2를 O(N^3)으로 해결 가능하다.
부분문제 3의 경우, 답은 음수인 점 p를 포함하거나 포함하지 않는 경우로 나누어진다. 점 p가 답에 포함될 경우, 다른 점들은 모두 양수이므로 모든 점의 가중치의 합을 더한 것이 답이 된다. p가 답에 포함되지 않는 경우에는 p를 기준으로 4분면을 나눈 후, 대각선 방향으로 마주보지 않는, 이웃한 두 사분면의 합 중 최댓값이 답이 된다.
부분문제 4의 경우, 일차원 직선상에서 최대 연속 부분합을 구하면 맞힐 수 있다. x축 방향 으로 정렬한 후, 차례대로 가중치의 합을 누적하다가 음수가 되면 0으로 초기화한 후 진행 하면 된다. 시간복잡도는 O(N log N)이다.
부분문제 2의 O(N^3) 방법을 개선하면 O(N^2 log N)에 답을 구할 수 있다. 고정된 윗변 Yi에 대해 아랫변 Y2를 늘려가면서 Binary Indexed Tree나 Segment Tree를 이용하여, 트리를 구성하는 각 구간 [X1,X2]의 가장 왼쪽에서 시작하는 최대 연속 부분합(LSUM), 가장 오른 쪽에서 시작하는 최대 연속 부분합(RSUM), 전체 구간의 최대 연속 부분합 (MAXSUM), 구간에 속한 모든 노드들의 합(SUM)을 동시에 갱신한다.
구간A의 왼쪽 자식 구간을 L , 오른쪽 자식 구간을 R이라 하면, 구간 A의 값은 구간 L 과 R의 값을 이용해 아래와 같이 계산할 수 있다.
A.SUM = L.SUM + R.SUM A.LSUM = max(L.LSUM , L.SUM + r.LSUM) A.RSUM = max(R.RSUM , R.SUM + L.RSUM) A.MAXSUM = max( L.RSUM + R.LSUM , L.MAXSUM,R.MAXSUM,A.SUM)트리의 데이터 갱신에는 O(log N)이 필요하며 직사각형 (0,Y1) - (10^9 , Y2) 속에 있는 최대 연속 부분합 (최대 가중치 합을 가지는 직사각형)은 트리의 데이터 갱신 후 루트 노드의 MAXSUM��값이 된다. 이 방법을 통해 O(N^2 log N)에 문제의 답을 구할 수 있다.