O(row^3*col^2) solution. maxSubArray O(row^2) should be able to optimize.


  • 0
    H

    The solution came out immediately after I saw this video. https://www.youtube.com/watch?v=yCQN096CwWM

        public int maxSumSubmatrix(int[][] matrix, int k) {
            int row = matrix.length;
            int col = matrix[0].length;
            int[] arr = new int[row];
            
            //the total complexity would be O(row^3*col^2), space is O(row)
            for (int i = 0; i < col; i++) {
                arr = new int[row];
                for (int j = i; j < col; j++) {
                    for (int l = 0; l < row; l++) {
                        arr[l] += matrix[l][j];
                    }
                    int temp = findMaxSubArray(arr, k);
                    if (temp == k) {
                        return k;
                    }
                    maxValue = Math.max(maxValue, temp);
                }
            }
            return maxValue;
        }
        
        public int findMaxSubArray(int[] arr, int k) {
           //this function should be able to optimize. I just used brute force. O(row^2);
           int maxSum = Integer.MIN_VALUE;
           for (int i = 0; i < arr.length; i++) {
               int cumSum = 0;
               for(int j = i; j < arr.length; j++) {
                   cumSum += arr[j];
                   if (cumSum <= k) {
                       maxSum = Math.max(cumSum, maxSum);
                   }
               }
           }
           return maxSum;
        }```

Log in to reply
 

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