程序员面试金典

程序员面试金典--最大和子矩阵

题目描述

有一个正整数和负整数组成的NxN矩阵，请编写代码找出元素总和最大的子矩阵。请尝试使用一个高效算法。

给定一个int矩阵mat和矩阵的阶数n，请返回元素总和最大的子矩阵的元素之和。保证元素绝对值小于等于100000，且矩阵阶数小于等于200。

测试样例：

[[1,2,-3],[3,4,-5],[-5,-6,-7]],3

返回：10

 

使用动态规划， O(n^3) 的时间复杂度。

 

class SubMatrix {
public:
    int maxSum(const vector<int>& vt, int n){
        int ans = 0, tmp = 0; 
        for(int i=0; i<n; ++i){
            if(tmp <= 0){
                tmp = vt[i]; 
            }else{
                tmp += vt[i]; 
            }
            if(tmp > ans){
                ans = tmp; 
            }
        }
        return ans; 
    }
    int sumOfSubMatrix(vector<vector<int> > mat, int n) {
        // write code here 
        int tmp, ans = 0; 
        for(int i=0; i<n; ++i){
            vector<int> arr(n, 0); 
            for(int j=i; j<n; ++j){
                for(int k=0; k<n; ++k){
                    arr[k] += mat[j][k]; 
                }
                tmp = maxSum(arr, n); 
                if(tmp > ans){
                    ans = tmp; 
                }
            }
        }
        return ans;  
    }
};