package question;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question363 {
 public static void main(String[] args) {
 int[][] ints = {
 {5,-4,-3,4},{-3,-4,4,5},{5,1,5,-4}
 };
 System.out.println(new Question363().maxSumSubmatrix4(ints, 10));
 }

 public int maxSumSubmatrix(int[][] matrix, int k) {
 int n = matrix.length;
 int m = matrix[0].length;
 int[][][][] dp = new int[n + 1][m + 1][n + 1][m + 1];
 int res = Integer.MIN_VALUE;
 for (int i1 = 1; i1 <= n; i1++) {
 for (int j1 = 1; j1 <= m; j1++) {
 dp[i1][j1][i1][j1] = matrix[i1 - 1][j1 - 1];
 for (int i2 = i1; i2 <= n; i2++) {
 for (int j2 = j1; j2 <= m; j2++) {
 dp[i1][j1][i2][j2] = dp[i1][j1][i2 - 1][j2] + dp[i1][j1][i2][j2 - 1] - dp[i1][j1][i2 - 1][j2 - 1] + matrix[i2 - 1][j2 - 1];
 if (dp[i1][j1][i2][j2] <= k && dp[i1][j1][i2][j2] > res) res = dp[i1][j1][i2][j2];
 }
 }
 }
 }
 return res;
 }

 public int maxSumSubmatrix2(int[][] matrix, int k) {
 int n = matrix.length;
 int m = matrix[0].length;
 int res = Integer.MIN_VALUE;
 for (int i1 = 1; i1 <= n; i1++) {
 for (int j1 = 1; j1 <= m; j1++) {
 int[][] dp = new int[n + 1][m + 1];
 dp[i1][j1] = matrix[i1 - 1][j1 - 1];
 for (int i2 = i1; i2 <= n; i2++) {
 for (int j2 = j1; j2 <= m; j2++) {
 dp[i2][j2] = dp[i2 - 1][j2] + dp[i2][j2 - 1] - dp[i2 - 1][j2 - 1] + matrix[i2 - 1][j2 - 1];
 if (dp[i2][j2] <= k && dp[i2][j2] > res) res = dp[i2][j2];
 }
 }
 }
 }
 return res;
 }

 public int maxSumSubmatrix3(int[][] matrix, int k) {
 int n = matrix.length;
 int m = matrix[0].length;
 int res = Integer.MIN_VALUE;
 for (int l = 0; l < m; l++) {
 int[] arr = new int[n];
 for (int r = l; r < m; r++) {
 for (int i = 0; i < n; i++) {
 arr[i] += matrix[i][r];
 }
 for (int i = 0; i < n; i++) {
 int sum = 0;
 for (int j = i; j < n; j++) {
 sum += arr[j];
 if (sum <= k && sum > res) res = sum;
 }
 }
 }
 }
 return res;
 }

 public int maxSumSubmatrix4(int[][] matrix, int k) {
 int n = matrix.length;
 int m = matrix[0].length;
 int res = Integer.MIN_VALUE;
 for (int t = 0; t < n; t++) {
 int[] arr = new int[m];
 for (int b = t; b < n; b++) {
 for (int i = 0; i < m; i++) {
 arr[i] += matrix[b][i];
 }
 for (int i = 0; i < m; i++) {
 int sum = 0;
 for (int j = i; j < m; j++) {
 sum += arr[j];
 if (sum <= k && sum > res) res = sum;
 if (res == k) return res;
 }
 }
 }
 }
 return res;
 }
}