1. Runtime Distribution

2. Submission Details

3. Description

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

4. Example

Given matrix = [
[1, 0, 1],
[0, -2, 3]
]
k = 2

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public int maxSumSubmatrix(int[][] matrix, int k) {

	int rowLength = matrix.length, colLength = matrix[0].length;

	int result = Integer.MIN_VALUE;

	int[] prefixSum = new int[rowLength + 1];

	for (int i = 0; i < colLength; i++) {

		int[] rowSum = new int[rowLength];
		for (int j = i; j < colLength; j++) {

			for (int r = 0; r < rowLength; r++) {
				rowSum[r] += matrix[r][j];
				prefixSum[r + 1] = prefixSum[r] + rowSum[r];
			}

			result = Math.max(result, mergeSort(prefixSum, 0, rowLength + 1, k));
			if (result == k) {
				return k;
			}
		}
	}
	return result;
}

private static int mergeSort(int[] prefixSum, int l, int r, int sum) {

	if (l + 1 == r) {
		return Integer.MIN_VALUE;
	}

	int mid = l + ((r - l) >> 1);

	int result = mergeSort(prefixSum, l, mid, sum);

	if (result == sum) {
		return sum;
	}

	result = Math.max(result, mergeSort(prefixSum, mid, r, sum));

	if (result == sum) {
		return sum;
	}

	int[] mergedArray = new int[r - l];

	int index = 0, k = mid;
	for (int i = l, j = mid; i < mid; i++) {
		while (j < r && prefixSum[j] - prefixSum[i] <= sum)
			j++;
		if (j - 1 >= mid) {
			result = Math.max(result, prefixSum[j - 1] - prefixSum[i]);
			if (result == sum) {
				return sum;
			}
		}

		while (k < r && prefixSum[k] < prefixSum[i]) {
			mergedArray[index++] = prefixSum[k++];
		}

		mergedArray[index++] = prefixSum[i];
	}

	while (k < r){
		mergedArray[index++] = prefixSum[k++];
	}

	System.arraycopy(mergedArray, 0, prefixSum, l, index);

	return result;
}

[/restab]
[restab title="Java"]

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

import org.junit.Test;

public class LeetCode0363_1 {
	
	public int maxSumSubmatrix(int[][] matrix, int k) {

		int rowLength = matrix.length, colLength = matrix[0].length;

		int result = Integer.MIN_VALUE;

		int[] prefixSum = new int[rowLength + 1];
		
		for (int i = 0; i < colLength; i++) {
			
			int[] rowSum = new int[rowLength];
			for (int j = i; j < colLength; j++) {
				
				for (int r = 0; r < rowLength; r++) {
					rowSum[r] += matrix[r][j];
					prefixSum[r + 1] = prefixSum[r] + rowSum[r];
				}

				result = Math.max(result, mergeSort(prefixSum, 0, rowLength + 1, k));
				if (result == k) {
					return k;
				}
			}
		}
		return result;
	}

	private static int mergeSort(int[] prefixSum, int l, int r, int sum) {

		if (l + 1 == r) {
			return Integer.MIN_VALUE;
		}

		int mid = l + ((r - l) >> 1);

		int result = mergeSort(prefixSum, l, mid, sum);

		if (result == sum) {
			return sum;
		}

		result = Math.max(result, mergeSort(prefixSum, mid, r, sum));

		if (result == sum) {
			return sum;
		}

		int[] mergedArray = new int[r - l];

		int index = 0, k = mid;
		for (int i = l, j = mid; i < mid; i++) {
			while (j < r && prefixSum[j] - prefixSum[i] <= sum)
				j++;
			if (j - 1 >= mid) {
				result = Math.max(result, prefixSum[j - 1] - prefixSum[i]);
				if (result == sum) {
					return sum;
				}
			}

			while (k < r && prefixSum[k] < prefixSum[i]) {
				mergedArray[index++] = prefixSum[k++];
			}

			mergedArray[index++] = prefixSum[i];
		}

		while (k < r){
			mergedArray[index++] = prefixSum[k++];
		}

		System.arraycopy(mergedArray, 0, prefixSum, l, index);

		return result;
	}

	@Test
	public void test() {
		int martix[][] = { { 2, 2, -1 } };
		System.out.println(maxSumSubmatrix(martix, 0));
	}

}

[/restab]
[restab title="Java"]

[/restab]
[/restabs]