【LeetCode】连续子数组、子矩阵最大和问题

曾经终败给现在 2022-11-13 13:29 217阅读 0赞

## 【LeetCode】连续子数组、子矩阵最大和问题 ##

### 文章目录 ###

*   *  【LeetCode】连续子数组、子矩阵最大和问题
     *   *  连续子数组的最大和★
         *  最大子矩阵★★★
         *  最大黑方阵★★

### 连续子数组的最大和★ ###

[剑指 Offer 42. 连续子数组的最大和][Offer 42.]

【**题目**】输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为`O(n)`。

**提示：**

*  `1 <= arr.length <= 10^5`
 *  `-100 <= arr[i] <= 100`

【**示例**】

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

【**解题思路**】

方法一：

动态规划，空间复杂度O(n)

class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int res = dp[0];
            for (int i = 1; i < nums.length; i++) {
        
                //保证和是连续的
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

方法二：空间复杂度O(1)

class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int dp = nums[0];
            int res = nums[0];
            for (int i = 1; i < nums.length; i++) {
        
                if (dp >= 0) {
        
                    dp += nums[i];
                } else {
        
                    dp = nums[i];
                }
                if (dp > res) res = dp;
            }
            return res;
        }
    }

--------------------

### 最大子矩阵★★★ ###

[面试题 17.24. 最大子矩阵][17.24.]

【**题目**】给定一个正整数、负整数和 0 组成的 `N × M` 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 `[r1, c1, r2, c2]`，其中 `r1`, `c1` 分别代表子矩阵左上角的行号和列号，`r2`, `c2` 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改

**说明：**

*  `1 <= matrix.length, matrix[0].length <= 200`

【**示例**】

输入：
    [
       [-1,0],
       [0,-1]
    ]
    输出：[0,1,0,1]
    解释：输入中标粗的元素即为输出所表示的矩阵

【**解题思路**】

上一题是一维求最大和，这一题是二维求最大和。显然可以通过转换来将二维映射为一维。

使用一个数据`sums`来保存当前i行至j行的列元素之和，求最大值并保存下标即可。

class Solution {
        
        public int[] getMaxMatrix(int[][] matrix) {
        
            int m = matrix.length, n = matrix[0].length;
            int[] pos = new int[4];
            int res = Integer.MIN_VALUE, dp = 0;
            int[] sums = new int[n];
            int begin_r = 0, begin_c = 0;
    
            for (int i = 0; i < m; i++) {
        
                Arrays.fill(sums, 0);
                for (int j = i; j < m; j++) {
        
                    dp = 0;
                    for (int k = 0; k < n; k++) {
        
                        sums[k] += matrix[j][k];
                        if (dp > 0) {
        
                            dp += sums[k];
                        } else {
        
                            dp = sums[k];
                            begin_r = i;
                            begin_c = k;
                        }
                        if (dp > res) {
        
                            res = dp;
                            pos[0] = begin_r;
                            pos[1] = begin_c;
                            pos[2] = j;
                            pos[3] = k;
                        }
                    }
                }
            }
            
            return pos;
        }
    }

--------------------

### 最大黑方阵★★ ###

[面试题 17.23. 最大黑方阵][17.23.]

【**题目**】给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 `[r, c, size]` ，其中 `r`, `c` 分别代表子方阵左上角的行号和列号，`size` 是子方阵的边长。若有多个满足条件的子方阵，返回 `r` 最小的，若 `r` 相同，返回 `c` 最小的子方阵。若无满足条件的子方阵，返回空数组。

**提示：**

*  `matrix.length == matrix[0].length <= 200`

【**示例**】

输入:
    [
       [1,0,1],
       [0,0,1],
       [0,0,1]
    ]
    输出: [1,0,2]
    解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵

【**解题思路**】

使用`二维数组left`保存左边连续0个数

使用`二维数组top`保存上面连续0个数，

若当前位置左边和上边连续0个数均大于暂时结果`res[2]`，则判断其黑方阵另外两条边是否符合要求

class Solution {
        
        public int[] findSquare(int[][] matrix) {
        
            if (matrix == null) return null;
            int n = matrix.length;
            if (n == 1 && matrix[0][0] == 1) return new int[]{
        };
            if (n == 1 && matrix[0][0] == 0) return new int[]{
        0, 0, 1};
    
            int[][] left = new int[n + 1][n + 1];
            int[][] top  = new int[n + 1][n + 1];
            int[] res = new int[3];
            int sz = 0;
    
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (matrix[i][j] == 0) {
        
                        left[i + 1][j + 1] = left[i + 1][j] + 1;
                        top[i + 1][j + 1]  = top[i][j + 1] + 1;
                        sz = Math.min(left[i + 1][j + 1], top[i + 1][j + 1]);
                        if (sz > res[2]) {
        
                            int r = i - sz + 1;
                            int c = j - sz + 1;
                            while (sz > res[2]) {
        
                                if (left[r + 1][j + 1] >= sz && top[i + 1][c + 1] >= sz) {
        
                                    res[0] = r;
                                    res[1] = c;
                                    res[2] = sz;
                                    break;
                                }
                                sz--;
                                r++;
                                c++;
                            }
                        }
                    }
                }
            }
    
            return res[2] == 0 ? new int[]{
        } : res;
        }
    }

[Offer 42.]: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
[17.24.]: https://leetcode-cn.com/problems/max-submatrix-lcci/
[17.23.]: https://leetcode-cn.com/problems/max-black-square-lcci/