using cumulative sum and TreeSet


  • 2
    F

    To find the max sum of an array, we can do as follows:

    • compute the cumulative sum of the array
    • find a pair of i and j, constrained to i<j, and cum[j]-cum[i]<=k
    • do some trick, the inequation above is actually cum[j]-k<=cum[i], we need to find the minimum value of cum[i] in order to maximize cum[j]-cum[i], that is, find TreeSet.ceiling(cum[j]-k)
    • if founded in the treeset, the value is actually cum[i], by subtract cum[i] from cum[j], we update the result
      The Max sum of rectangle on larger than k can be transformed into the problem of finding the max sum of an array no larger than k by slicing the matrix:
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int m = matrix.length;
            int n = matrix[0].length;
            int result = Integer.MIN_VALUE;
            for (int begin = 0; begin < n; begin++) {
                for (int end = begin + 1; end <= n; end++) {
                    int[] arr = new int[m];
                    for (int i = 0; i < m; i++) {
                        for (int j = begin; j < end; j++) {
                            arr[i] += matrix[i][j];
                        }
                    }
                    TreeSet<Integer> treeSet = new TreeSet<>();
                    treeSet.add(0);
                    int cumulative = 0;
                    for (int i : arr) {
                        cumulative += i;
                        Integer ceiling = treeSet.ceiling(cumulative - k);
                        if (ceiling != null) {
                            result = Math.max(result, cumulative - ceiling);
                        }
                        treeSet.add(cumulative);
                    }
                }
            }
            return result;
        }

Log in to reply
 

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