Java 81ms, Beats previously submitted java solutions


  • 1
    A
    public class Solution {
    
        public static int maxSumSubArrayNoGreaterThanK(int[] s, int k) {
            int len     = s.length;
            int ans     = Integer.MIN_VALUE;
            int nums[] = new int[len];
            nums[0] = s[0];
            for(int i=1;i<len;i++){
                nums[i] = nums[i-1] + s[i];
            }
    
            for(int i=0;i<len;i++){
                for(int j=i;j<len;j++){
                    int sum;
                    if(i==0) sum = nums[j];
                    else sum = nums[j] - nums[i-1];
                    if(sum > ans && sum <= k)
                        ans = sum;
                }
            }
            return ans;
        }
    
    
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int cols    = matrix[0].length;
            int rows    = matrix.length;
            int maxSum  = Integer.MIN_VALUE;
    
            for (int leftCol = 0; leftCol < cols; leftCol++) {
                int[] tmp = new int[rows];
                for (int rightCol = leftCol; rightCol < cols; rightCol++) {
                    for (int l = 0; l < rows; l++) {
                        tmp[l] += matrix[l][rightCol];
                    }
                    int currentResult = maxSumSubArrayNoGreaterThanK(tmp,k);
                    if (currentResult > maxSum) {
                        maxSum = currentResult;
                    }
                }
            }
            return maxSum;
        }
    }
    

  • 0
    D

    @asraful.ruet Took me sometime to understand your solution... But very clever way of traversing through the various rectangles.

    [1, 0, 1],
    [0, -2, 3]

    The loops in the maxSumSubMatrix calculate the row sum for each rectangle having all rows, starting from column 1 to last column

    So for the above example first the entire matrix is considered, whose row sum is
    [2]
    [1]

    Then in the next loop the row sum for each rectangle having all rows, starting from column 2 to last column =>
    [1, | 0, 1], =[1]
    [0, | -2, 3] [1]

    Then for the last iteration row sum for all rectangles, starting from column 3 to end, i.e this is just the last column:
    [1]
    [3]

    After each row sum is calculated, the function maxSumSubArrayNoGreaterThanK, calculates the sum upto each row after adding the previous rows:
    nums[i] = nums[i-1] + s[i]
    and then considers all combinations of rectangles starting from first row to last, then second row to last, and so on ....

    This way by first considering all column combinations and then all row combinations, all the rectangles in the matrix are taken care of


Log in to reply
 

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