서브 매트릭스 NxN 행렬의 최대 합계와 N-nonzero 값을 갖는 N-nonzero 값 만있는 경우 O (N^2)

Question

각 행에 정확히 하나의 0이 아닌 요소가 있고 각 열에 정확히 1이 아닌 0 요소 요소는 양수 또는 음수 일 수 있음). 우리는 최대 합계 부분 행렬을 찾고 싶습니다. 얼마나 효율적으로 그렇게 할 수 있습니까?

매트릭스의 크기는 N × N이며 0이 아닌 요소는 N 개만 있습니다. N은 너무 커서 O (N) 알고리즘을 사용할 수 없습니다. 누구든지 O (N), O (N log N) 또는이 시간 복잡성을 해결하는 방법을 알고 있습니까?

감사합니다.

Answer 1

최대 합계 부분합을 찾으려면 여기 maximum sum subrectangle in a sparse matrix에 설명 된 알고리즘을 사용하여 O (n^2 log n) 시간에 수행 할 수 있습니다. 이것은 O (n^3) 인 Kadane 알고리즘을 이깁니다.