Leetcode_面试题 17.24. 最大子矩阵

最大子矩阵问题，n是200，枚举上下行，O(N)求一下最大子段和。

code

class Solution {

public:

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

        int n=matrix.size();

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

        vector<int> ans(4,0);

        int res=-0x3f3f3f3f;

        //枚举上下界

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

            vector<int> h(m,0);

            for(int j=i;j<n;j++){

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

                    h[k]+=matrix[j][k];

                }

                //最大子段和

                int tmp=0;

                int l=0;

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

                    tmp+=h[k];

                    if(tmp>res){

                        res=tmp;

                        ans[0]=i;

                        ans[1]=l;

                        ans[2]=j;

                        ans[3]=k;

                    }

                    if(tmp<0){

                        tmp=0;

                        l=k+1;

                    }

                }

            }

        }

        return ans;

    }

};

巴特西

Leetcode_面试题 17.24. 最大子矩阵

最新文章

热门文章