Untitled

mail@pastecode.io avatar
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