2 차원 배열에 대한 Kadane의 알고리즘 이해

maximum subarray problem을 해결하는 프로그램을 작성하려고합니다. 저는 2-D 배열에서 O (N^4) 구현뿐만 아니라 1-D 배열에 대한 Kadane 's Algorithm의 직관을 이해할 수 있습니다. 그러나 2 차원 배열에서 O (N^3) 구현을 이해하는 데 문제가 있습니다.2 차원 배열에 대한 Kadane의 알고리즘 이해

1) 같은 열의 이전 행에있는 요소로 요소를 추가하는 이유는 무엇입니까?

for (int i = 1; i <= N; i++) { 
    for (int j = 1; j <= M; j++) 
     array[i][j] += array[i-1][j]; 
}

2)은 웹에 대한 설명은하지만 아무 소용이 찾고 알고리즘 시도

의 두 번째 부분 전혀 이해가되지 않습니다. 희망이 좀 도와주세요!

미리 감사드립니다.

출처

2013-09-28 boxme

Kadane의 알고리즘을 사용하여 1D 배열에서 최대 합 서브 어레이를 계산하는 방법을 알고 있습니다. 이제이 알고리즘을 2D 배열로 확장하려고합니다. O (N^3) 알고리즘의 경우 직감이 있습니다. 우리가 N^2 하위 문제를 만든 다음 O (N) Kadane의 알고리즘을 실행하려고하면 최대 하위 배열 문제를 해결할 수 있습니다.

기본적으로 N^2 하위 문제를 만드는 방법은 행렬의 위쪽과 아래쪽 행을 모두 반복하는 것입니다. 그런 다음 kadane의 1D 알고리즘을 적용하여 하위 배열이 존재하는 최적의 열을 찾습니다. 따라서 우리는이 두 행 사이의 수를 합쳐서 합쳐서이 새로 형성된 1D 배열에 kadane의 1D 알고리즘을 적용합니다.

하지만 여기에는 문제가 있습니다. 위쪽과 아래쪽 행의 모든 O (n^2) 범위에 대한 합계를 계산하는 것은 O (n^4)가됩니다. 이 병목 목은 각 요소를 해당 요소의 열에서 그 위에있는 모든 숫자의 합으로 대체하여 행렬을 수정하면 극복 할 수 있습니다. 따라서 이제는 행렬에서 적절한 배열을 빼서 O (n) 시간에 두 행 사이의 수의 합을 알아낼 수 있습니다.

자바 의사 코드 -

int kadane2D(int array[N+1][M+1]){ 

     // Modify the array's elements to now hold the sum 
     // of all the numbers that are above that element in its column 
     for (int i = 1; i <= N; i++) { 
      for (int j = 1; j <= M; j++){ 
       array[i][j] += array[i-1][j]; 
      } 
     } 


     int ans = 0; // Holds the maximum sum matrix found till now 

     for(int top=1; top<=N; top++){ 
      for(int bottom=top; bottom<=N; bottom++){ 
       // loop over all the N^2 sub problems 
       int[] sums = new int[N+1]; 

       // store the sum of numbers between the two rows 
       // in the sums array 
       for(int i=0; i<=N; i++){ 
        sums[i] = array[bottom][i] - array[top-1][i]; 
       } 

       // O(n) time to run 1D kadane's on this sums array 
       ans = Math.max(ans, kadane1d(sums)); 
      } 
     } 
     return ans; 
    }

출처

2014-02-21 16:50:27

2 차원 배열에 대한 Kadane의 알고리즘 이해

답변

관련 문제