面试题 17.24. 最大子矩阵

面试题 17.24. 最大子矩阵

思路:

本题是最大连续子数组的二维follow up.

一维情况下,可以直接使用多种算法求解:

  1. 累加数组+二维搜索左右边界, $O(N^2)$

  2. 二维搜索左右边界同时累加数字,$O(N^2)$

  3. 分治算法,把问题maxarr(i, j)分解为maxarr(i, mid)maxarr(mid + 1, j)。其中子数组可能在左右两端数组中或者横跨两个段,所以从中间向两边搜索最大连续数组和Sum1,如此解决了一个基本问题,并且递归的将小问题解决,获取总的问题的解。$O(NLogN)$

  4. 线段树做法,同样也是分治的思想,但是考虑的更多。maxarr(i, j)分解为maxarr(i, mid)maxarr(mid + 1, j)。基本问题是arr(i, j)中的sumlsumr, sumisumm,分别代表从左边开始的子数组的和,从右边开始的子数组的和,在中间扩展的子数组的和,和整个数组的和。而我们要大问题的sumi就是所要求的值,巧妙的地方在于问题的分解,sumi可以就是子数组的sumi和左子段的sumr与右子段的suml之和最大值。其他同理。

  5. DP做法,以dp[i]arr[i]为结尾的和最大的连续子数组的和。状态更新方程为
    $$
    dp[i] = max(dp[i - 1] + arr[i], arr[i])
    $$

这很有趣,实际上就是舍弃掉可能为负数的dp[i - 1], 另外在舍弃时也可以记录下数组起点。更进一步的观察,空间可以优化到O(1)

二维情况下,虽然非常相似,但是解法一时想不到直接扩展到二维。但是问题可以化解为一维。

在确定了矩阵行数据,或者首先遍历矩阵的上下界后,顺道求出该矩阵的在各各列的和。之后便可以用一维的做法求出连续列的最大和。

复杂$O(N^3)$。

代码:

class Solution {
    int n;
    int m;
    vector<int> b;
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        n = matrix.size();
        m = matrix[0].size();
        b.resize(m);
        
        vector<int> ans(4);
        int maxval = matrix[0][0];
        for(int i = 0; i < n; ++i){            
            for(int j = i; j < n; ++j){
                // accumulate the matrix in vertical sequences.
                if(i == j){
                    for(int k = 0; k < m; ++k) b[k] = matrix[i][k];
                }else
                    for(int k = 0; k < m; ++k) b[k] += matrix[j][k];
                int sum = 0;
                int begin = 0;
                for(int l = 0; l < m; ++l){
                    
                    // sum = max(b[l], b[l] + sum);
                    if(sum < 0){
                        sum = 0;
                        begin = l;
                    }
                    sum += b[l];

                    if(sum > maxval){
                        maxval = sum;
                        ans[0] = i;
                        ans[1] = begin;
                        ans[2] = j;
                        ans[3] = l;
                    }
                }        
            }
        }
        return ans;
    }
};

Comments