희소 행렬의 최대 합 부분 직사각형

Question

NxN 행렬에서 최대 합 부분 직사각형을 찾는 것은 다른 게시물에서 지적한대로 2-d kadane의 알고리즘을 사용하여 O(n^3) 시간으로 수행 할 수 있습니다. 그러나 행렬이 희박한 경우, 특히 O(n) 0이 아닌 항목 인 경우 O(n^3) 시간을 맞출 수 있습니까?

만약 내가 관심이있는 현재의 응용 프로그램에 도움이된다면 행렬의 각 행과 각 열에서 하나가 아닌 0 값을 가정하는 솔루션이면 충분할 것입니다. 그러나, 내 미래의 응용 프로그램에서는이 가정이 적절하지 않을 수 있습니다 (단지 희소성이 유지 될 것입니다). 어쨌든 수학적 직관은 희소성을 단순히 악용하는 좋은 해결책이있을 수 있으며 행렬이 대각선 및 순열 행렬의 곱이다.

Answer 1

예, 더 잘 수행 할 수 있습니다. 모든

먼저, O(1)의 배열의 최대 배열의 합을 찾기 O(logn) 시간

에

1. 업데이트 기본 1D 배열의 단일 값으로 우리를 허용하는 데이터 구조에 대해 생각해 봅시다 시간

사실, 아래처럼 보이는 균형 이진 트리가 작업을 수행 할 수 있습니다. 트리 구조는 다음과 같이 설명 할 수 있습니다.

1. 트리의 모든 리프 노드는 배열의 모든 요소를 ​​나타냅니다.
2. 내부 노드가 범위 [a, b]을 커버하는 경우 왼쪽 자식은 [a, c] 범위를 커버하고 오른쪽 자식 커버 범위는 [c + 1, b]입니다. 여기에서 c = floor((a + b)/2))입니다.

3. 루트 노드는 범위 [1, n]을 포함합니다.

        O 
           / \ 
          /  \ 
          /   \ 
         /    \ 
         /     \ 
         O      O 
        / \     / \ 
       / \    / \ 
       /  \    /  \ 
       O   O   O   O 
   /\  /\  /\  /\ 
   o  o  o  o  o  o  o  o 
   A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 
   

(리프 노드와 내부 노드를 포함하여) 모든 노드 v 부착 4 개 필드 있습니다

• S[v]는 : v의 범위 내의 모든 값의 합
• M[v] : 최대 부분 배열 합계가 v의 범위
• L[v] : 최대 값 v의 왼쪽에서 시작 m 서브 어레이 '
• R[v]의 범위 : 최대 배열의 합 v 오른쪽에서 종료 "상기 정의 기준의 범위

, 우리는를 찾을 수도 다음 업데이트 규칙 :

모든 잎 노드 v, S[v] = A[v]를 들어

• , M[v] = L[v] = R[v] = max{0, A[v]}
• 내부 노드 v 및 그 아이을및 r는 마지막으로

R[v] = max{R[r], R[l] + S[r]}

L[v] = max{L[l], L[r] + S[l]}

S[v] = S[l] + S[r]

M[v] = max{M[l], M[r], R[l] + L[r]}

• 
  , 우리는 처음에 언급 한 작업을 구현할 수 있습니다.
  • A[i]을 업데이트하려면 트리에서 해당 리프 노드를 찾은 다음 위의 규칙을 사용하여 경로를 따라 필드를 업데이트 할 수 있습니다.
  • 최대 서브 어레이 합계는 단순히 M[root]입니다.

  이제이 데이터 구조를 사용하여 최대 사각형을 찾는 방법에 대해 알아 보겠습니다. 사각형의 위쪽 행과 아래쪽 행을 i 번째 및 j 번째 행으로 고정하면 문제는 1D 최대 부분합 ​​합 문제가됩니다 (여기서 A[k] = sum{B[i..j, k]}). 핵심 통찰력은 고정 i에 대해 j을 오름차순으로 열거하면 위의 데이터 구조를 사용하여 기본 1D 배열을 유지하고 대답을 신속하게 찾을 수 있습니다.

  result = 0 
  for i in (1, 2, ..., n) 
      set all fields of the binary tree T to 0 
      for j in (i, i + 1, ..., n) 
       for any k where B[j, k] != 0 
        T.update(k, A[k] + B[j, k]) 
       result = max{M[root], result} 
  return result 
  

  이 알고리즘의 시간 복잡도는 O(mn logn)되면, 행렬 m 비제로 요소들을 포함한다고 가정 의사 코드 개념을 설명한다. 귀하의 경우 m = O(n)이므로 시간 복잡도는 O(n^2 logn)이며 O(n^3)보다 좋습니다.