# using cumulative sum and TreeSet

• 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<>();
int cumulative = 0;
for (int i : arr) {
cumulative += i;
Integer ceiling = treeSet.ceiling(cumulative - k);
if (ceiling != null) {
result = Math.max(result, cumulative - ceiling);
}