가장 큰 합

Question

가능한 중복과 행렬 찾기 :

Finding a submatrix with the maximum possible sum in O(n^2)

가 내가되는 N × N 행렬을 가지고 있습니다. 위의 행렬의 요소가 가장 큰 MxM 부분 행렬을 찾고 싶습니다.

효율적인 알고리즘은 무엇입니까?

Answer 1

나는 평소와 같이 계산 N.에게

먼저 행렬을 확대 할 때 M과 차 시간을 확대 할 때 일정 시간에서 실행되는 알고리즘을 가지고있다. 합계를 저장하십시오. 그런 다음 한 행 필드를 오른쪽으로 이동합니다. 두 개의 MxM 행렬이 겹치기 때문에 두 개의 겹치지 않는 두 열을 합할 수 있습니다. 모든 금액을 저장하십시오. 이제 라인의 최대 합을 선택할 수 있습니다.

다음 줄로 이동하십시오. 저장된 총액을 기억하십니까? 첫 번째 줄과 두 번째 줄의 MxM 행렬이 다시 겹치기 때문에 MxM 행렬의 첫 번째 줄과 마지막 줄을 더하고 두 번째 줄의 첫 번째 합을 계산할 수 있습니다.

이제 두 번째 줄의 두 번째 합계로 이동하십시오. 위와 동일한 작업을 수행하지만 첫 번째 합계의 마지막 줄과 두 번째 줄의 두 번째 합계가 다시 겹치는 것을 알 수 있습니다.

내가 혼란 스럽다는 것을 알고 있습니다. 이해하지 못하면 약간의 그림을 그려 볼 것입니다. 알고리즘은 this answer의 용지를 기반으로합니다.

편집 : 내가 사진을 약속 알고 있지만이 충분해야한다 :

AB 
CD 

첫째 :

 
A AB AB AB AB B 
AC ABCD ABCD ABCD ABCD BD 
AC ABCD ABCD ABCD ABCD BD 
AC ABCD ABCD ABCD ABCD BD 
AC ABCD ABCD ABCD ABCD BD 
C CD CD CD CD D 

다음은이 같은 위치 사 submatices, A, B, C, D,있다 A 서브 매트릭스의 합계를 계산합니다 : sum (A). 최적화가 없습니다. 이제 B : sum (B)의 합계를 계산하려고합니다. A와 동일하게 할 수 있지만 A와 B가 겹치는 것을 볼 수 있습니다. 따라서 sum (B)에 sum (A)을 지정하고 A AC AC AC AC 세로 벡터의 합계를 계산하고 sum (B)에서 substract를 계산 한 다음 세로 벡터 B BD BD BD BD의 합을 계산하여 sum (B)에 추가합니다.

 
sum(B) = sum(A) - sum(A AC AC AC AC) + sum(B BD BD BD BD) 

당신은 합계 (B)가 있습니다. 이제 하위 명령의 전체 첫 번째 줄을 계속해서 계산할 수 있습니다.

두 번째 줄로 이동 : matices C와 D. 이전 줄에서는 sum (A)를 저장 했으므로 전체 matice C를 더할 필요가 없습니다. 그들은 다시 겹쳐 있음을 주목하십시오. A와 C의 차이를 추가하면됩니다.

//code (1) 
subC = sum([A AB AB AB AB]) //as substract C 
addC = sum([C CD CD CD CD]) //as add C 
sum(C) = sum(A) - subC + addC 

당신은 합계 (C)가 있습니다.

//code (2) 
subD = sum([AB AB AB AB B]) //as substract D 
addD = sum([CD CD CD CD D]) //as add D 
sum(D) = sum(B) - subD + addD 

을하지만, ADDC 대 SUBC 및 addD 대 SUBD 비교 : 지금 당신은 다음과 같이 합 (D)를 얻을 수 있습니다. 그것들은 중첩됩니다! 이렇게하면 다음과 같이 할 수 있습니다.

하나의 서브 매트릭스 합계를 계산하기위한 25 개의 지시 대신, 6을 사용합니다.가능한 모든 크기의 MxM에 대해 첫 번째 행렬에 대해서는 MxM, 첫 번째 행에 대해서는 M * 2 + 2 행, 나머지 행렬에 대해서는 첫 번째 열과 여섯 개의 행렬이 사용됩니다.