Сумма отличительных SubMatrix - PullRequest
Новая
       28

Сумма отличительных SubMatrix

0 голосов
/ 14 октября 2019

Учитывая прямоугольную матрицу m и int, k, возвращаем сумму различных чисел, содержащихся в каждой подкатрице k, которая суммируется с максимальным значением

Я попытался придуматьхорошее решение для этой проблемы, но оно кажется уклончивым, я не могу кодировать эффективное решение, я знаю, как эффективен dp, но получение эффективного суммирования только уникальных значений кажется трудным, мое грубое силовое решение показано ниже, может ли кто-нибудь помочь сэлегантное решение этой проблемы Контрольный пример 

int[][] matrix =
{
    {1,2,-1,4},
    {-8,-3,4,2},
    {3,8,10,-8},
    {-4,-1,1,7}
};                                        
Output: 20


static int  maximumSum(int[][] matrix, int K) {
        if (K > matrix.length) return -1;
        //build prefix matrix
        int N = matrix.length;
        int M = matrix[0].length;
        int[][] prefixMat = new int[N][M];
        Set<Integer>set = new HashSet<>();
        Set<Integer>res = new HashSet<>();

        for(int i = 0; i< N; i++){
            for(int j =0; j < M ; j++){
                int row = K+i;
                int col = K+j;
                if(row <= N && col <= N){
                    for(int k = i; k < row; k++){
                        for(int m =j; m < col ; m ++){
                            System.out.print(k +""+ m +" ");
                            int val = matrix[k][m];
                            set.add(val);
                        }
                    }
                    System.out.println();
                    int max = set.stream().mapToInt(Integer::intValue).sum();
                    res.add(max);

                    set.clear();
                    row =0;
                    col =0;
                }
                else {
                    continue;
                }
            }
        }
        int out = res.stream().mapToInt(Integer::intValue).max().getAsInt();
        System.out.println(out);
        return out;
    }

Грубая сила работает

...