kadane 2D

이전 포스트에서 kadane algorithm을 소개했었는데 이번에는 2D matrix 확장. 아래 문제를 보자.

Given a 2D array, find the maximum sum submatrix in it.

example>
{ 1,  2, -1, -4, -20},
{-8, -3,  4,  2,   1},
{ 3,  8, 10,  1,   3},
{-4, -1,  1,  7,  -6}

위의경우, (1,1)에 있는 -3부터 (3,3)에 있는 7까지의 submatrix가 최대 합이된다.

naive

(start x, start y), (end x, end y)를 바꿔가면서 하면 for loop 4번. time complexity는 O(N^4)가 된다.

kadane 2D

kadane으로 1d array를 O(N^2)에서 O(N)으로 만들었듯이, 2D는 O(N^4)를 O(N^3)으로 만들 수 있다. left, right좌표를 옮겨가면서 row를 kadane 알고리즘을 적용하면 된다. 이때 column 값들을 accumulate하면서 하면 더 효율적으로 할 수 있는데 아래 코드를 보면 이해가 갈듯.

int kadane2d(int[][] m){
    int row = m.length;
    if(row==0)return 0;
    int col = m[0].length;

    int ret = Integer.MIN_VALUE;
    for (int left = 0; left < col; left++) {
        int[] sum = new int[row]; // reuse this 
        for (int right = left; right < col; right++) {
            for (int i = 0; i < row; i++) {
                sum[i] += m[i][right];
            }

            int curMax=sum[0];
            int max=sum[0];
            for (int i = 1; i < row; i++) {
                curMax = Math.max(curMax+sum[i], sum[i]);
                max = Math.max(curMax, max);
            }
            ret=Math.max(ret, max);
        }
    }

    return ret;
}

Problems

• maximum sum submatrix @geeks
• Max Sum of Rectangle No Larger Than K @leetcode : Kadane 응용

Reference

• my implementation & test cases