C# solution, both row and col use Kadane's algo


  • 0
    L
    public int MaxSumSubmatrix(int[,] matrix, int k) {
        int liRow = matrix.GetLength(0);
        int liCol = matrix.GetLength(1);
    
        int[,] liaTotal = new int[liRow, liCol];
        int[] liaSum = new int[liRow];
    
        int liResult = int.MinValue;
    
        for(int i = 0; i < liRow; ++i) {
            liaTotal[i, 0] = matrix[i, 0];
            for(int j = 1; j < liCol; ++j) {
                liaTotal[i, j] += liaTotal[i, j - 1] + matrix[i, j];
            }
        }
    
        for(int i = 0; i < liCol; ++i) {
            for(int j = -1; j < i; ++j) {
                for(int m = 0; m < liRow; ++m) {
                    liaSum[m] = liaTotal[m, i] - (j == -1 ? 0 : liaTotal[m, j]) + (m == 0 ? 0 : liaSum[m - 1]);
                }
    
                for(int m = 0; m < liRow; ++m) {
                    for(int n = -1; n < m; ++n) {
                        int liValue = liaSum[m] - (n == -1 ? 0 : liaSum[n]);
                        if(liValue == k)
                            return k;
                        if(liValue <= k)
                            liResult = Math.Max(liResult, liValue);
                    }
                }
    
            }
        }
        return liResult;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.