<Hard> Max Sum of Rectangle No Larger Than K (LeetCode : C#)

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/

📕 문제 설명

m, n 크기의 행렬과 정수 k가 주어질 때 행렬 안의 직사각형 내 값들의 합 중 k보다 크지 않은 최대 합 반환하기

• Input
  행렬 정보, k
• Output
  행렬 안 직사각형의 합 중 k보다 크지 않은 최대 합

예제

풀이

public class Solution {
    public int MaxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.Length, n = matrix[0].Length;
        int[,] prefixSum = new int[m + 1, n + 1];
        
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                // matrix[0][0] ~ matrix[i-1][j-1] 까지의 합 
                prefixSum[i, j] = prefixSum[i - 1, j] + prefixSum[i, j - 1] - prefixSum[i - 1, j - 1] + matrix[i - 1][j - 1];
            }
        }
        
        int max = int.MinValue;
        HashSet<int> set = new HashSet<int>();
        for (int r1 = 1; r1 <= m; r1++)
        {
            for (int r2 = r1; r2 <= m; r2++)
            {
                set.Clear();
                set.Add(0);
                
                for (int col = 1; col <= n; col++)
                {
                    // 구간합 계산 (r2 ~ (r1-1)), col 증가시키면서
                    int rangeSum = prefixSum[r2, col] - prefixSum[r1 - 1, col];
                    
                    foreach (int num in set)
                    {
                        int sum = rangeSum - num; // 현재 rangesum 기준 이전 rangesum들 빼주면서 모든 경우 check하게됨 
                        if(sum <= k) max = Math.Max(max, sum); // k보다 작은 sum 중 더 큰 것으로 갱신
                    }
                    
                    set.Add(rangeSum);
                }
            }
        }
        
        return max;
    }
}

결과

아직 표본이 별로 없어서 무의미하다..