Untitled
unknown
plain_text
a month ago
2.3 kB
3
Indexable
Never
public static int get_ans(int N, List<List<Integer>> A) { int[][][] maxInSubgrid = new int[N][N][N]; int[][][] minInSubgrid = new int[N][N][N]; // Populate max and min values for all possible sub-grids for (int size = 1; size <= N; size++) { for (int i = 0; i <= N - size; i++) { for (int j = 0; j <= N - size; j++) { int maxVal = Integer.MIN_VALUE; int minVal = Integer.MAX_VALUE; for (int k = 0; k < size; k++) { for (int l = 0; l < size; l++) { maxVal = Math.max(maxVal, A.get(i + k).get(j + l)); minVal = Math.min(minVal, A.get(i + k).get(j + l)); } } maxInSubgrid[i][j][size - 1] = maxVal; minInSubgrid[i][j][size - 1] = minVal; } } } int maxSum = 0; // Dynamic Programming to maintain the best maximum beauty sum avoiding overlapping sub-grids for (int size1 = 1; size1 <= N; size1++) { for (int r1 = 0; r1 + size1 <= N; r1++) { for (int c1 = 0; c1 + size1 <= N; c1++) { int b1 = maxInSubgrid[r1][c1][size1 - 1] - minInSubgrid[r1][c1][size1 - 1]; for (int size2 = 1; size2 <= N; size2++) { for (int r2 = 0; r2 + size2 <= N; r2++) { if (overlap(r1, c1, size1, r2, 0, size2)) continue; for (int c2 = 0; c2 + size2 <= N; c2++) { if (overlap(r1, c1, size1, r2, c2, size2)) continue; int b2 = maxInSubgrid[r2][c2][size2 - 1] - minInSubgrid[r2][c2][size2 - 1]; maxSum = Math.max(maxSum, b1 + b2); } } } } } } return maxSum; } // Utility function to check if two sub-grids overlap private static boolean overlap(int r1, int c1, int size1, int r2, int c2, int size2) { return !(r1 + size1 <= r2 || r2 + size2 <= r1 || c1 + size1 <= c2 || c2 + size2 <= c1); }
Leave a Comment