0

指定された nxn 行列から最大の Submatrix Sum を取得しようとしています。私が読んだところによると、アルゴリズムの複雑さは n^3 (kadane) です。ここでスタックオーバーフローで見つけたコードを使用して Java で実装しようとしました (C# の Anders Gustafsson によってこれらの投稿で書かれました) が、常に機能するとは限りません。

私のコードはこれです： 

public static void maxSubMatrix(int matrix[][]) {
    // O(n^3) Max Sum Submatrix

    int row = matrix.length;
    int col = matrix[0].length; // Get the col-length by taking the length of 
                                // row 0 (in programm the matrices will be n x n)

    // Initialise maxSum
    int maxSum = 0;

    // Set left column
    for (int left=0; left<col; left++) {

        // Initialise array
        int tempArray[] = new int[row];

        // Set right column by left column (outer loop)
        for (int right=left; right<col; right++){

            // Calculate sum between current left-right for every row 'i'
            for (int i=0; i<row; i++)
                tempArray[i] = matrix[i][right];
            // ----

            // Find maximum sum in tempArray[]
            int sum = maxSubArray(tempArray);

            // Compare sum with maxSum so far, and update it if necessary
            if (sum > maxSum) maxSum = sum;
        }
    }
    System.out.println(maxSum);
}
// ==========================

public static int maxSubArray(int array[]){
    // Kadane O(n) Max Sum Subarray
    int maxSum = 0;
    int tempSum = 0;

    for (int i=0; i<array.length; i++){
        int b = array[i];
        if (tempSum + b > 0) tempSum += b;
        else tempSum = 0;
        maxSum = Math.max(maxSum, tempSum);
    }
    return maxSum;
}

3 つの例があります。

行列 1
-2 -3
-1 -4
出力は 0 (空の 0x0 行列も解)

マトリックス 2
2 -1
-2 -1
出力は 2

行列 3
-1 3
3 -1
出力は 3 ですが、4 にする必要があります

多分誰かがエラーを見ることができます。また、それを実装するためのまったく新しいアイデアにもオープンです。

4

1 に答える 1

0

次の右の要素を一時配列に追加するのを忘れただけです。

(int i=0; i<row; i++)
            tempArray[i] += matrix[i][right];

今、すべてが大丈夫です！;)

グリーツ

于 2014-03-30T21:08:11.810 に答える