363. Max Sum of Rectangle No Larger Than K

乍看是一題複雜度很高的題目，實際上也真的很高，第一次遇到 judge 時間超過1000ms將近2000ms竟然沒有TLE還AC的題目。但也有可能是我做的題目不夠多，少見多怪罷了

題目給定一個 m 列 (row) 和 n 行 (column) 的矩陣 matrix，和一個 k 值，要求返回一個子矩陣內的值相加最接近或等於 k 的值但不大於 k，已知測資矩陣內的每個值皆不大於 k

這種求和的問題第一個直覺都是想到用prefix sum來解決，只不過平常都是用在一維陣列，這題很巧妙地考驗操作 2-d 陣列的技巧，只要稍微在紙上演練一下就可以想出來了

舉個簡單的例子

可以依列對每一行的值累加，然後得到這樣的prefix sum table

如果子矩陣取 (R1, C0)~(R2, C1) (4 + 5 + 7 + 8)，只要計算 prefix sum table 中的 (R3, C0) - (R1, C0) + (R3, C1) - (R1, C1) 即可，也就是 (12 - 1) + (15 - 2)

找出規則後就可以開工了，首先建立 prefix sum table

1
2
3
4
5
6

int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> preSum(m + 1, vector<int>(n, 0));

for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        preSum[i + 1][j] = preSum[i][j] + matrix[i][j];

這裡要注意的是因為對每一行進行累加，所以 table 的列數要比原本的列數多一

然後用 4 個迴圈按照 (r1, c1), (r2, c2) 的順序找出答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int ans = INT_MIN;
for (int r1 = 0; r1 < m; r1++)
    for (int r2 = r1 + 1; r2 <= m; r2++)
        for (int c1 = 0; c1 < n; c1++) {
            int val = 0;
            for (int c2 = c1; c2 < n; c2++) {
                val += preSum[r2][c2] - preSum[r1][c2];

                if (val < k) {
                    ans = max(ans, val);
                } else if (val == k) {
                    return k;
                }
            }
        }

因為 table 比原本的 matrix 多了一列，所以 r2 的上界是 <= m ，這應該沒甚麼問題，另外這也將子矩陣取單一個數的情況也考慮到了，例如當 k 為 8 的情況，子矩陣應該為 matrix 的 (R2, C1) ，在迴圈裡就是 preSum[3][1] - preSum[2][1]

題目的 hint 有提到 ordered set 和 binary search ，不過我看了一下 discussion 看不出個所以然就放棄了… 改天有空再研究研究

這題的難度大概 90% 來自繁瑣的迴圈過程，沒有紙筆輔助大概很難光靠空想推導出來，當然我是說我自己啦