Получение подматрицы с максимальной суммой?

вот объяснение, чтобы пойти с опубликованным кодом. Есть два ключевых трюка, чтобы сделать эту работу эффективно: (I) алгоритм Кадане и (II) с использованием префиксных сумм. Вам также нужно (III) применить трюки к матрице.

Часть I: алгоритм Кадане

алгоритм Кадане-это способ найти непрерывную подпоследовательность с максимальной суммой. Давайте начнем с подхода грубой силы для нахождения максимальной смежной подпоследовательности, а затем рассмотрим оптимизацию это чтобы получить алгоритм Кадане.

Предположим, у вас есть последовательность:

-1,  2,  3, -2

для подхода грубой силы пройдите вдоль последовательности, генерирующей все возможные подпоследовательности, как показано ниже. Учитывая все возможности, мы можем начать, расширить или закончить список с каждым шагом.

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
Possible subsequences:
-1   [sum -1]

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
Possible subsequences:
-1 (end)      [sum -1]
-1,  2        [sum  1]
 2            [sum  2]

At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
Possible subsequences:
-1, (end)       [sum -1]
-1,  2 (end)    [sum -1]
 2 (end)        [sum 2]
-1,  2,  3      [sum 4]
 2,  3          [sum 5]
 3              [sum 3]

At index 3, we consider appending the -2
-1,  2,  3, -2
             ^
Possible subsequences:
-1, (end)          [sum -1]
-1,  2 (end)       [sum  1]
 2 (end)           [sum  2]
-1,  2  3 (end)    [sum  4]
 2,  3 (end)       [sum  5]
 3, (end)          [sum  3]
-1,  2,  3, -2     [sum  2]
 2,  3, -2         [sum  3]
 3, -2             [sum  1]
-2                 [sum -2]

для этого подхода грубой силы мы, наконец, выбираем список с лучшей суммой,(2, 3) и вот ответ. Однако, чтобы сделать это эффективным, считайте, что вы действительно не нужно держать каждый из списков. Из списков, которые не закончились, вам нужно только сохранить лучший, другие не могут сделать лучше. Из списков, которые закончились, вам может понадобиться только сохранить лучший, и только если он лучше, чем те, которые не закончились.

Итак, вы можете отслеживать то, что вам нужно, только с массивом позиций и массивом сумм. Массив позиций определяется следующим образом:position[r] = s отслеживает список, который заканчивается r и начинается s. И,sum[r] дает сумму для подпоследовательности, заканчивающейся на index r. Этот оптимизированный подход является алгоритмом Кадане.

пробегая пример снова отслеживая наш прогресс таким образом:

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2


At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5

Again, we choose to extend because that gives a higher sum that starting a new one.
-1,  2,  3, -2
             ^
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5
positions[3] = 3     sum[3] = 3

опять же, лучшая сумма-5, а список - от индекса 1 до индекса 2, который равен (2, 3).

Часть II: префикс суммы

мы хотим иметь способ расчета суммы по строке, для любой начальной точки в любую конечная точка. Я хочу вычислить эту сумму за O(1) время, а не просто добавить, что занимает O (m) время, где m-количество элементов в сумме. С некоторыми предварительными вычислениями это может быть достигнуто. Вот как это делается. Предположим, у вас есть матрица:

a   d   g
b   e   h 
c   f   i

вы можете предварительно вычислить эту матрицу:

a      d      g
a+b    d+e    g+h
a+b+c  d+e+f  g+h+i

как только это будет сделано, вы можете получить сумму, идущую по любому столбцу от любого начала до конечной точки в столбце, просто вычитая два значения.

Часть III: Объединение трюков, чтобы найти максимальную подматрицу

предположим, что вы знаете верхнюю и нижнюю строки подматрицы max. Вы могли бы сделать это:

1. игнорировать строки над верхней строкой и игнорировать строки ниже нижней ряд.
2. С какой матрицей остается, рассмотрим использование суммы каждого столбца, чтобы сформируйте последовательность (что-то вроде строки, представляющей несколько строк). (Вы можете быстро вычислить любой элемент этой последовательности с префиксом суммы подход.)
3. используйте подход Кадана, чтобы выяснить лучшую подпоследовательность в этом последовательность. Индексы, которые вы получите, скажут вам влево и вправо позиции лучшей подматрицы.

теперь, как насчет того, чтобы на самом деле выяснить верхний и нижний ряд? Просто попробуйте все возможности. Попробуйте поместить верхнюю часть везде, где вы можете, и положить нижнюю часть везде, где вы можете, и запустить процедуру Kadane-base, описанную ранее для каждой возможности. Когда вы находите Макс, вы отслеживаете верхнее и нижнее положение.

поиск строки и столбца занимает O (M^2), где M-количество строк. Нахождение столбца занимает O (N) времени, где N-количество столбцов. Таким образом, общее время равно O(M^2 * N). И, если M=N, требуется время O (N^3).

уже есть много ответов, но вот еще одна реализация Java, которую я написал. Он сравнивает 3 варианта решения:

1. наивный (грубая сила) - O(n^6) Время
2. очевидное решение DP-o(n^4) Время и O (n^3) пространство
3. более умное решение DP, основанное на алгоритме Кадана-o(n^3) Время и O (n^2) пространство

есть примеры выполнения для n = 10 через n = 70 с шагом 10 с хорошим выходом, сравнивающим время выполнения и пространство требования.

код:

public class MaxSubarray2D {

    static int LENGTH;
    final static int MAX_VAL = 10;

    public static void main(String[] args) {

        for (int i = 10; i <= 70; i += 10) {
            LENGTH = i;

            int[][] a = new int[LENGTH][LENGTH];

            for (int row = 0; row < LENGTH; row++) {
                for (int col = 0; col < LENGTH; col++) {
                    a[row][col] = (int) (Math.random() * (MAX_VAL + 1));
                    if (Math.random() > 0.5D) {
                        a[row][col] = -a[row][col];
                    }
                    //System.out.printf("%4d", a[row][col]);
                }
                //System.out.println();
            }
            System.out.println("N = " + LENGTH);
            System.out.println("-------");

            long start, end;
            start = System.currentTimeMillis();
            naiveSolution(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   no auxiliary space requirements");
            start = System.currentTimeMillis();
            dynamicProgammingSolution(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   requires auxiliary space for "
                    + ((int) Math.pow(LENGTH, 4)) + " integers");
            start = System.currentTimeMillis();
            kadane2D(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   requires auxiliary space for " +
                    + ((int) Math.pow(LENGTH, 2)) + " integers");
            System.out.println();
            System.out.println();
        }
    }

    // O(N^2) !!!
    public static void kadane2D(int[][] a) {
        int[][] s = new int[LENGTH + 1][LENGTH]; // [ending row][sum from row zero to ending row] (rows 1-indexed!)
        for (int r = 0; r < LENGTH + 1; r++) {
            for (int c = 0; c < LENGTH; c++) {
                s[r][c] = 0;
            }
        }
        for (int r = 1; r < LENGTH + 1; r++) {
            for (int c = 0; c < LENGTH; c++) {
                s[r][c] = s[r - 1][c] + a[r - 1][c];
            }
        }
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;
        for (int r1 = 1; r1 < LENGTH + 1; r1++) { // rows 1-indexed!
            for (int r2 = r1; r2 < LENGTH + 1; r2++) { // rows 1-indexed!
                int[] s1 = new int[LENGTH];
                for (int c = 0; c < LENGTH; c++) {
                    s1[c] = s[r2][c] - s[r1 - 1][c];
                }
                int max = 0;
                int c1 = 0;
                for (int c = 0; c < LENGTH; c++) {
                    max = s1[c] + max;
                    if (max <= 0) {
                        max = 0;
                        c1 = c + 1;
                    }
                    if (max > maxSum) {
                        maxSum = max;
                        maxRowStart = r1 - 1;
                        maxColStart = c1;
                        maxRowEnd = r2 - 1;
                        maxColEnd = c;
                    }
                }
            }
        }

        System.out.print("KADANE SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }

    // O(N^4) !!!
    public static void dynamicProgammingSolution(int[][] a) {
        int[][][][] dynTable = new int[LENGTH][LENGTH][LENGTH + 1][LENGTH + 1]; // [row][col][height][width]
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 0; h < LENGTH + 1; h++) {
                    for (int w = 0; w < LENGTH + 1; w++) {
                        dynTable[r][c][h][w] = 0;
                    }
                }
            }
        }

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 1; h <= LENGTH - r; h++) {
                    int rowTotal = 0;
                    for (int w = 1; w <= LENGTH - c; w++) {
                        rowTotal += a[r + h - 1][c + w - 1];
                        dynTable[r][c][h][w] = rowTotal + dynTable[r][c][h - 1][w];
                    }
                }
            }
        }

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 0; h < LENGTH + 1; h++) {
                    for (int w = 0; w < LENGTH + 1; w++) {
                        if (dynTable[r][c][h][w] > maxSum) {
                            maxSum = dynTable[r][c][h][w];
                            maxRowStart = r;
                            maxColStart = c;
                            maxRowEnd = r + h - 1;
                            maxColEnd = c + w - 1;
                        }
                    }
                }
            }
        }

        System.out.print("    DP SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }


    // O(N^6) !!!
    public static void naiveSolution(int[][] a) {
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;

        for (int rowStart = 0; rowStart < LENGTH; rowStart++) {
            for (int colStart = 0; colStart < LENGTH; colStart++) {
                for (int rowEnd = 0; rowEnd < LENGTH; rowEnd++) {
                    for (int colEnd = 0; colEnd < LENGTH; colEnd++) {
                        int sum = 0;
                        for (int row = rowStart; row <= rowEnd; row++) {
                            for (int col = colStart; col <= colEnd; col++) {
                                sum += a[row][col];
                            }
                        }
                        if (sum > maxSum) {
                            maxSum = sum;
                            maxRowStart = rowStart;
                            maxColStart = colStart;
                            maxRowEnd = rowEnd;
                            maxColEnd = colEnd;
                        }
                    }
                }
            }
        }

        System.out.print(" NAIVE SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }

}

вот Java-версия реализации Ernesto с некоторыми изменениями:

public int[][] findMaximumSubMatrix(int[][] matrix){
    int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }

    int maxSum = matrix[0][0];
    int top = 0, left = 0, bottom = 0, right = 0; 

    //Auxiliary variables 
    int[] sum = new int[dim];
    int[] pos = new int[dim];
    int localMax;                        

    for (int i = 0; i < dim; i++) {
        for (int k = i; k < dim; k++) {
            // Kadane over all columns with the i..k rows
            reset(sum);
            reset(pos);
            localMax = 0;
            //we keep track of the position of the max value over each Kadane's execution
            // notice that we do not keep track of the max value, but only its position
            sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
            for (int j = 1; j < dim; j++) {                    
                if (sum[j-1] > 0){
                    sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = pos[j-1];
                }else{
                    sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = j;
                }
                if (sum[j] > sum[localMax]){
                    localMax = j;
                }
            }//Kadane ends here

            if (sum[localMax] > maxSum){
                  /* sum[localMax] is the new max value
                    the corresponding submatrix goes from rows i..k.
                     and from columns pos[localMax]..localMax
                     */
                maxSum = sum[localMax];
                top = i;
                left = pos[localMax];
                bottom = k;
                right = localMax;
            }      
        }
    }
    System.out.println("Max SubMatrix determinant = " + maxSum);
    //composing the required matrix
    int[][] output = new int[bottom - top + 1][right - left + 1];
    for(int i = top, k = 0; i <= bottom; i++, k++){
        for(int j = left, l = 0; j <= right ; j++, l++){                
            output[k][l] = matrix[i][j];
        }
    }
    return output;
}

private void reset(int[] a) {
    for (int index = 0; index < a.length; index++) {
        a[index] = 0;
    }
}

С помощью архив и Ларри и модификация алгоритма Кадана, вот мое решение:

int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }
    int maxSoFar = 0;
    int min , subMatrix;
    //iterate over the possible combinations applying Kadane's Alg.
    for (int i = 0; i < dim; i++) {
        for (int j = i; j < dim; j++) {
            min = 0;
            subMatrix = 0;
            for (int k = 0; k < dim; k++) {
                if (i == 0) {
                    subMatrix += ps[j][k];
                } else {
                    subMatrix += ps[j][k] - ps[i - 1 ][k];
                }
                if(subMatrix < min){
                    min = subMatrix;
                }
                if((subMatrix - min) > maxSoFar){
                    maxSoFar = subMatrix - min;
                }                    
            }
        }
    }

осталось только определить элементы подматрицы, т. е.: верхний левый и нижний правый угол подматрицы. Кто-нибудь предлагает?

Я собираюсь опубликовать ответ здесь и могу добавить фактический код c++, если он будет запрошен, потому что я недавно работал над этим. Некоторые слухи о разделении и Завоевателе, которые могут решить это в O(N^2), есть, но я не видел никакого кода для поддержки этого. По моему опыту, я нашел следующее.

    O(i^3j^3) -- naive brute force method
    o(i^2j^2) -- dynamic programming with memoization
    O(i^2j)   -- using max contiguous sub sequence for an array


if ( i == j ) 
O(n^6) -- naive
O(n^4) -- dynamic programming 
O(n^3) -- max contiguous sub sequence

посмотреть JAMA пакет; я верю, что это сделает вашу жизнь проще.

вот решение C#. Ref:http://www.algorithmist.com/index.php/UVa_108

public static MaxSumMatrix FindMaxSumSubmatrix(int[,] inMtrx)
{
    MaxSumMatrix maxSumMtrx = new MaxSumMatrix();

    // Step 1. Create SumMatrix - do the cumulative columnar summation 
    // S[i,j] = S[i-1,j]+ inMtrx[i-1,j];
    int m = inMtrx.GetUpperBound(0) + 2;
    int n = inMtrx.GetUpperBound(1)+1;
    int[,] sumMatrix = new int[m, n];

    for (int i = 1; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            sumMatrix[i, j] = sumMatrix[i - 1, j] + inMtrx[i - 1, j];
        }
    }

    PrintMatrix(sumMatrix);

    // Step 2. Create rowSpans starting each rowIdx. For these row spans, create a 1-D array r_ij            
    for (int x = 0; x < n; x++)
    {
        for (int y = x; y < n; y++)
        {
            int[] r_ij = new int[n];

            for (int k = 0; k < n; k++)
            {
                r_ij[k] = sumMatrix[y + 1,k] - sumMatrix[x, k];
            }

            // Step 3. Find MaxSubarray of this r_ij. If the sum is greater than the last recorded sum =>
            //          capture Sum, colStartIdx, ColEndIdx.
            //          capture current x as rowTopIdx, y as rowBottomIdx.
            MaxSum currMaxSum = KadanesAlgo.FindMaxSumSubarray(r_ij);

            if (currMaxSum.maxSum > maxSumMtrx.sum)
            {
                maxSumMtrx.sum = currMaxSum.maxSum;
                maxSumMtrx.colStart = currMaxSum.maxStartIdx;
                maxSumMtrx.colEnd = currMaxSum.maxEndIdx;
                maxSumMtrx.rowStart = x;
                maxSumMtrx.rowEnd = y;
            }
        }
    }

    return maxSumMtrx;
}

public static void PrintMatrix(int[,] matrix)
{
    int endRow = matrix.GetUpperBound(0);
    int endCol = matrix.GetUpperBound(1);
    PrintMatrix(matrix, 0, endRow, 0, endCol);
}

public static void PrintMatrix(int[,] matrix, int startRow, int endRow, int startCol, int endCol)
{
    StringBuilder sb = new StringBuilder();
    for (int i = startRow; i <= endRow; i++)
    {
        sb.Append(Environment.NewLine);
        for (int j = startCol; j <= endCol; j++)
        {
            sb.Append(string.Format("{0}  ", matrix[i,j]));
        }
    }

    Console.WriteLine(sb.ToString());
}

// Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum
public static MaxSum FindMaxSumSubarray(int[] inArr)
{
    int currMax = 0;
    int currStartIndex = 0;
    // initialize maxSum to -infinity, maxStart and maxEnd idx to 0.

    MaxSum mx = new MaxSum(int.MinValue, 0, 0);

    // travers through the array
    for (int currEndIndex = 0; currEndIndex < inArr.Length; currEndIndex++)
    {
        // add element value to the current max.
        currMax += inArr[currEndIndex];

        // if current max is more that the last maxSum calculated, set the maxSum and its idx
        if (currMax > mx.maxSum)
        {
            mx.maxSum = currMax;
            mx.maxStartIdx = currStartIndex;
            mx.maxEndIdx = currEndIndex;
        }

        if (currMax < 0) // if currMax is -ve, change it back to 0
        {
            currMax = 0;
            currStartIndex = currEndIndex + 1;
        }
    }

    return mx;
}

struct MaxSum
{
    public int maxSum;
    public int maxStartIdx;
    public int maxEndIdx;

    public MaxSum(int mxSum, int mxStart, int mxEnd)
    {
        this.maxSum = mxSum;
        this.maxStartIdx = mxStart;
        this.maxEndIdx = mxEnd;
    }
}

class MaxSumMatrix
{
    public int sum = int.MinValue;
    public int rowStart = -1;
    public int rowEnd = -1;
    public int colStart = -1;
    public int colEnd = -1;
}

Это моя реализация 2D алгоритма Кадане. Я думаю, что это более ясно. Концепция основана только на алгоритме кадане. Первый и второй цикл основной части (то есть в нижней части кода) состоит в том, чтобы выбрать каждую комбинацию строк, а третий цикл-использовать алгоритм 1D kadane по каждой следующей сумме столбцов (которая может быть вычислена в const time из-за предварительной обработки матрицы путем вычитания значений из двух выбранных (из комбинаций) строк). Вот код:

    int [][] m = {
            {1,-5,-5},
            {1,3,-5},
            {1,3,-5}
    };
    int N = m.length;

    // summing columns to be able to count sum between two rows in some column in const time
    for (int i=0; i<N; ++i)
        m[0][i] = m[0][i];
    for (int j=1; j<N; ++j)
        for (int i=0; i<N; ++i)
            m[j][i] = m[j][i] + m[j-1][i];

    int total_max = 0, sum;
    for (int i=0; i<N; ++i) {
        for (int k=i; k<N; ++k) { //for each combination of rows
            sum = 0;
            for (int j=0; j<N; j++) {       //kadane algorithm for every column
                sum += i==0 ? m[k][j] : m[k][j] - m[i-1][j]; //for first upper row is exception
                total_max = Math.max(sum, total_max);
            }
        }
    }

    System.out.println(total_max);

вот мое решение. Это O (n^3) во времени и O(n^2) пространстве. https://gist.github.com/toliuweijing/6097144

// 0th O(n) on all candidate bottoms @B.
// 1th O(n) on candidate tops @T.
// 2th O(n) on finding the maximum @left/@right match.
int maxRect(vector<vector<int> >& mat) {
    int n               = mat.size();
    vector<vector<int> >& colSum = mat;

    for (int i = 1 ; i < n ; ++i) 
    for (int j = 0 ; j < n ; ++j)
        colSum[i][j] += colSum[i-1][j];

    int optrect = 0;
    for (int b = 0 ; b < n ; ++b) {
        for (int t = 0 ; t <= b ; ++t) {
            int minLeft = 0;
            int rowSum[n];
            for (int i = 0 ; i < n ; ++i) {
                int col = t == 0 ? colSum[b][i] : colSum[b][i] - colSum[t-1][i];
                rowSum[i] = i == 0? col : col + rowSum[i-1];
                optrect = max(optrect, rowSum[i] - minLeft); 
                minLeft = min(minLeft, rowSum[i]);
            }
        }
    }

    return optrect;
}

Я бы просто проанализировал массив NxN, удалив-ves все, что остается, является самой высокой суммой субматрицы.

вопрос не говорит, что вы должны оставить исходную матрицу нетронутой или что порядок имеет значение.