2020-03-18 刷题2（矩阵，动态规划）

最大子矩阵

面试挂在这个题目上面了，其实仔细想想也没有那么难。

m行n列的矩阵，遍历i和j，将第i到j行的元素按列求和，压缩成一个一维向量，则可以把最大子串和算法应用在这个一维向量上，得到(l, r)为最大子串，也就是第i行到第j行的最大子矩阵，左上角：(i, l), 右下角：(j, r). 遍历每一种i和j的组合，从中取出最大值，就是整个矩阵的最大子矩阵和。

leetcode上这个题与原题稍有不同，要求返回最大子矩阵的左上角和右下角，多设置几个值记录一下就行了。

代码：

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        int h = matrix.size(), w = matrix.size() ? matrix[0].size() : 0;
        int max_sum = matrix[0][0], r1 = 0, c1 = 0, r2 = 0, c2 = 0;
        for(int i = 0; i < h; i++){
            vector<int> tmp(w, 0);
            for(int j = i; j < h; j++){
                int sum = 0, begin_idx = 0;
                for(int k = 0; k < w; k++){
                    // tmp: 第i行到第j行按列求和
                    tmp[k] += matrix[j][k];
                   // 最大子串和
                    if(sum < 0) {
                        sum = tmp[k];
                        begin_idx = k;
                    }
                    else sum += tmp[k];
                    if(sum > max_sum){
                        max_sum = sum;
                        r1 = i;
                        c1 = begin_idx;
                        r2 = j;
                        c2 = k;
                    }
                }
            }
        }
        // 返回左上角，右下角
        return {r1, c1, r2, c2};
    }
};

836 矩形重叠

判断两个矩形是否重叠，则需要判断它们在x轴的投影以及y轴的投影是否重叠，这也是计算两个矩形Intersect的方法。判断在x轴上的投影是否重叠，则判断左边界的最大值是否小于右边界的最小值即可。y轴的判断也是类似。

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        return(max(rec1[0], rec2[0]) < min(rec1[2], rec2[2]) &&
       max(rec1[1], rec2[1]) <  min(rec1[3], rec2[3]));
    }
};