瞭解Kadane的二維陣列算法

我正試圖編寫一個解決maximum subarray problem的程序。我可以理解一維陣列上Kadane算法背後的直覺以及二維陣列上的O（N^4）實現。但是，我在理解2-D數組上的O（N^3）實現方面遇到了一些麻煩。瞭解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算法計算一維數組上的最大和子數組。現在我們想要擴展2D數組的這個算法。對於O（N^3）算法，我們有一個直覺。如果我們以某種方式創建N^2個子問題，然後嘗試運行我們的O（N）Kadane算法，我們可以解決最大子陣列問題。

所以基本上我們如何創建N^2子問題是通過遍歷矩陣的所有頂部和底部行。然後我們嘗試通過應用kadane的1D算法來找到子陣列之間的最佳列。因此我們將這兩列之間的數字求和，然後在這個新形成的一維數組上應用kadane的1D算法。

但我們在這裏有一個問題。計算頂部和底部行的所有O（n^2）範圍的總和本身將是O（n^4）。這個瓶頸可以通過修改我們的矩陣來克服，用每個元素替換元素列中所有數字之和。因此，現在我們可以通過減去矩陣中適當的數組來找出O（n）時間中任意兩行之間的數字總和。

的java的僞碼 -

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

瞭解Kadane的二維陣列算法

回答

相關問題