摘要：思路一暴力循環如果我們將矩陣中的每個子矩陣都枚舉出來，并計算其元素和，從而得出小于的最大值即可。

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
             and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

現有一個由整數構成的矩陣，問從中找到一個子矩陣，要求該子矩陣中各個元素的和為不超過k的最大值，問子矩陣中元素的和為多少?
注：后面的文章中將使用[左上角頂點坐標，右下角頂點坐標]來表示一個矩陣，如[(1,2),(3,4)]表示左上角頂掉坐標為(1,2)，右下角頂點坐標為(3,4)的矩陣。用S[(1,2),(3,4)]表示該矩陣的面積。頂點的坐標系以數組的起始點作為起點，向下為x軸正方向，向右為y軸正方向。

如果我們將矩陣中的每個子矩陣都枚舉出來，并計算其元素和，從而得出小于K的最大值即可。
這里通過一個額外的二維數組S緩存了[(0,0), (i,j)]的矩形的面積，可以通過O(n^2)的時間復雜度完成計算，即S[i][j] = matrix[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]， 則矩形[(r1,c1),(r2,c2)]的面積為S[r2][c2] -S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1]。這種算法的時間復雜度為O(N^4)，因為需要定位矩形的四個頂點，一共需要四圈循環，代碼如下：

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int row = matrix.length;
        if(row == 0) return 0;
        int col = matrix[0].length;
        if(col == 0) return 0;
        
        //rectangle[i][j]記錄頂點為[0,0],[i,j]的矩形的面積
        int[][] rectangle = new int[row][col];
        for(int i = 0 ; i0) {
                    area += rectangle[i-1][j];
                }
                if(j>0) {
                    area += rectangle[i][j-1];
                }
                //減去重復計算的面積
                if(i>0 && j>0) {
                    area -= rectangle[i-1][j-1];
                }
                
                rectangle[i][j] = area;
            }
        }
        
        
        int result = Integer.MIN_VALUE;
        for(int startRow = 0 ; startRow 0) {
                            area -= rectangle[startRow-1][endCol];
                        }
                        if(startCol > 0) {
                            area -= rectangle[endRow][startCol-1];
                        }
                        if(startRow > 0 && startCol > 0) {
                            area += rectangle[startRow-1][startCol-1];
                        }
                        if (area <= k)
                            result = Math.max(result, area);
                    }
                }
            }
        }
        return result;
    }

對算法從時間上優化的核心思路就是盡可能的減少比較或是計算的次數。上面一個思路的我們可以理解為以row1和row2分別作為子矩陣的上邊界和下邊界，以col2作為右邊界，要求找到一個左邊界col1，使得其劃分出來的子矩陣中元素的和為小于等于k的最大值，即

max(S[(row1,0),(row2, col2)] - S[(row1,0),(row2, col1)]) 
&& col1 < col2 
&& S[(row1,0),(row2, col2)] - S[(row1,0),(row2, col1)]
換句話說，假如將col2左側的所有以最左側邊為起點的子矩陣按照元素和從小到大排隊，即將子矩陣(row1, 0), (row2, colx) 其中colx < col2按照元素和從小到大排序，此時只需要在該結果中找到一個矩陣，其值為大于等于S[(row1,0),(row2, col2)] - k的最小值。此時得出的矩陣元素和差最大。這里采用TreeSet來實現O(logN)的元素查找時間復雜度。
代碼如下：
    public int maxSumSubmatrix2(int[][] matrix, int k) {
        int row = matrix.length;
        if(row == 0) return 0;
        int col = matrix[0].length;
        if(col == 0) return 0;
        
        //rectangle[i][j]記錄頂點為[0,0],[i,j]的矩形的面積
        int[][] rectangle = new int[row][col];
        for(int i = 0 ; i0) {
                    area += rectangle[i-1][j];
                }
                if(j>0) {
                    area += rectangle[i][j-1];
                }
                //減去重復計算的面積
                if(i>0 && j>0) {
                    area -= rectangle[i-1][j-1];
                }
                
                rectangle[i][j] = area;
            }
        }
        
        
        int result = Integer.MIN_VALUE;
        for(int startRow = 0 ; startRow < row ; startRow++) {
            for(int endRow = startRow ; endRow < row ; endRow++) {
                //記錄從startRow到endRow之間所有以最左側邊為起點的矩形的面積
                TreeSet treeSet = new TreeSet();
                treeSet.add(0);
                for(int endCol = 0 ; endCol < col ; endCol++) {
                    int area = rectangle[endRow][endCol];
                    if(startRow > 0) {
                        area -= rectangle[startRow-1][endCol];
                    }
                    //可以減去的左側矩形的最小面積，即大于S[(row1,0),(row2, col2)] - k的最小值
                    Integer remain = treeSet.ceiling(area - k);
                    if(remain != null) {
                        result = Math.max(result, area - remain);
                    }
                    treeSet.add(area);
                }
            }
        }
        return result;
    }
思路三：分治法
從上面兩種思路，我們可以將題目演化成另一種思路，即對于任意以row1和row2作為上下邊界的子矩陣，將其中每一列的元素的和記為sum[colx](0<=colx，則生成一個長度為col的整數數組sum。需要從該整數數組中找到一個連續的子數組，使得該子數組的和最大且不超過k。

連續子數組的和是一道非常經典的動態規劃的問題，它可以在nlogn的時間復雜度內解決。這里采用歸并排序的思路來進行解決。本質上將數組以中間位置分割為左子數組和右子數組，分別求左子數組內和右子數組內最大的連續子數組和，并且在遞歸的過程中將左右子數組中的元素分別從小到大排序。接著判斷是否有橫跨中間節點的子數組滿足題目要求，因為左右子數組分別有序，因此一旦遇到一個右邊界，其和左邊界構成的矩陣的元素的和超過k，就可以停止右指針的移動。因此每次中間結果的遍歷只需要O(N)的時間復雜度。
代碼如下：
    public int maxSumSubmatrix3(int[][] matrix, int k) {
        int row = matrix.length;
        if(row == 0) return 0;
        int col = matrix[0].length;
        if(col == 0) return 0;
        int result = Integer.MIN_VALUE;
        int[] sums = new int[row+1];//sums[i]記錄startCol到endCol列之間，0行到i行構成的矩陣的面積
        for(int startCol = 0 ; startCol mid) {
                ans = Math.max(sums[j-1] - sums[i], ans);
                if (ans == k) return k;
            }
            while(m