问一道G家面试题 - 未名空间(mitbbs.com)

问一道G家面试题 - 未名空间(mitbbs.com)
一个matrix，每个matrix[i][j]有一个价格，给你一个budget，问如何求出最大面积的
子矩阵，使得子矩阵的价格之和不超过budget.

Same as max sum rectangle -
One change:get max value that is less than or equal budget.
http://likemyblogger.blogspot.com/2015/08/mj-26-maximum-sum-rectangle-in-2d-matrix.html

    int kadane(vector<int> &col){

        int max_ending_here = INT_MIN, max_ending_sofar = INT_MIN;

        for(auto i:col){

            if(max_ending_here<0) max_ending_here = 0;

            max_ending_here += i;

            max_ending_sofar = max(max_ending_sofar, max_ending_here);

        }

        return max_ending_sofar;

    }

 

    int maxSum2D(vector<vector<int>> &matrix){

        int m = matrix.size();

        if(m==0) return 0;

        int n = matrix[0].size();

        if(n==0) return 0;

 

        int ret = INT_MIN;

        for(int l=0; l<n; ++l){

            vector<int> col(m, 0);

            for(int r=l; r<n; ++r){

                for(int i=0; i<m; ++i){

                    col[i] += matrix[i][r];

                }

                ret = max(ret, kadane(col));

            }

        }

        return ret;

    }

这题看起来和leetcode的Maximal Rectangle 很像，但似乎不可能找到类似的复杂度的
解法。

能想到的solution
1.preprocess：建立一个matrix［］［］存［0］［0］到［i］［j］的sum，这个可以
用dp解决，复杂度O（n^2）
2.check 以每一点为右下点的最大可能的矩阵，这个每个点都是O（i＊lg（j））的复
杂度了吧。除了可以用个binary search来减少一点复杂度，我也想不到别的办法了。

Read full article from 问一道G家面试题 - 未名空间(mitbbs.com)