O (n^2)의 가능한 최대 합계를 갖는 부분 행렬 찾기

Question

MxN 행렬이 주어질 때 가장 큰 합계를 가진 (연속적인) 부분 행렬을 찾을 수있는 Java로 프로그램을 작성하려고합니다. 그런 다음 프로그램은 서브 매트릭스의 왼쪽 위 모서리 좌표와 오른쪽 하단 모서리 좌표를 리턴해야합니다. 행렬은 음수를 포함 할 수 있으며 행렬과 부분 행렬은 정사각형 일 필요는 없습니다.

나는 이것이 여기에서 논의되었다는 것을 알았다 : Getting the submatrix with maximum sum? 그리고 해결책은 O (n^3) 인 것 같다. 내 친구는 한 때 O (n^2)에서이 문제를 해결할 수 있었다고 말했습니다. 또한 here.을 제안 할 수 있습니까?

이 문제를 가장 효율적으로 해결할 수있는 코드가 있습니까?

Answer 1

O(n^2)에서 문제를 해결할 수는 없지만 최소한 알고리즘은 알려져 있지 않습니다. 최적의 솔루션은 하위 입방 복잡성을 가지고 있지만 구현하기가 매우 어렵고 실제로는 느려질 수 있습니다. 그것에 관한 논문을 읽을 수 있습니다 here.

사용 된 일반적인 알고리즘은 사용자가 발견 한 질문에서 참조한 O(n^3)입니다.

Answer 2

은 (S) 그는 그래서 그냥/그녀를 물어, 너무 우리와 함께 공유 할 :)

이