当前位置：首页 > article >正文

Kadane 算法二维详解

article 2024/11/22 21:28:01

Kadane 算法扩展到二维问题

二维 Kadane 算法用于解决矩阵中的 最大子矩阵和问题，即从给定矩阵中找出一个矩形区域，使得其所有元素的和最大。

问题描述

给定一个二维矩阵 matrix，其中包含正数、负数和零，找出一个矩形区域，使其所有元素的和最大，并返回最大和。

例如：

输入:
matrix = [
    [1,  2, -1, -4, -20],
    [-8, -3, 4,  2,   1],
    [3,   8, 10, 1,   3],
    [-4, -1, 1,  7,  -6]
]

输出: 29
解释: 最大子矩阵是 [[3, 8, 10], [-4, -1, 1]]，和为 29。

Kadane 算法在二维中的扩展思路

1. 固定行边界

通过枚举上下边界，将二维问题转换为一维问题：

将矩阵的某个子矩阵压缩为一维数组。
压缩方式：对矩阵的列按行区间求和。

2. 使用一维 Kadane 算法

对每列的累积和进行处理，利用一维 Kadane 算法找到最大子数组和，从而求解当前行区间的最大子矩阵和。

算法步骤

初始化变量：
- maxSum：存储全局最大子矩阵和。
- left 和 right：记录矩阵左右边界。
- top 和 bottom：记录矩阵上下边界。
固定矩阵的左右边界：
- 枚举左边界 left 和右边界 right。
- 压缩列到一维数组 temp，使 temp[i] 表示行 i 在 left 到 right 列之间的累积和。
使用 Kadane 算法计算 temp 的最大子数组和，同时记录上下边界 top 和 bottom。
更新全局最大值 maxSum 和对应的边界。
返回最大子矩阵和。

代码实现

public class MaxSumRectangle {
    public static int maxSumRectangle(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        int maxSum = Integer.MIN_VALUE;
        int left = 0, right = 0, top = 0, bottom = 0;

        // 固定左右边界
        for (int l = 0; l < cols; l++) {
            // 初始化列的累积和数组
            int[] temp = new int[rows];

            for (int r = l; r < cols; r++) {
                // 更新列的累积和
                for (int i = 0; i < rows; i++) {
                    temp[i] += matrix[i][r];
                }

                // 使用 Kadane 算法计算一维数组的最大子数组和
                int[] kadaneResult = kadane(temp);
                int currentSum = kadaneResult[0];
                int start = kadaneResult[1];
                int end = kadaneResult[2];

                // 更新全局最大值
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                    left = l;
                    right = r;
                    top = start;
                    bottom = end;
                }
            }
        }

        // 打印最大子矩阵边界
        System.out.println("Top: " + top + ", Bottom: " + bottom);
        System.out.println("Left: " + left + ", Right: " + right);

        return maxSum;
    }

    // 一维 Kadane 算法，返回最大和及其起始和结束索引
    private static int[] kadane(int[] nums) {
        int maxSum = nums[0], currentSum = nums[0];
        int start = 0, end = 0, tempStart = 0;

        for (int i = 1; i < nums.length; i++) {
            if (currentSum + nums[i] > nums[i]) {
                currentSum += nums[i];
            } else {
                currentSum = nums[i];
                tempStart = i;
            }

            if (currentSum > maxSum) {
                maxSum = currentSum;
                start = tempStart;
                end = i;
            }
        }

        return new int[]{maxSum, start, end};
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, -1, -4, -20},
            {-8, -3, 4, 2, 1},
            {3, 8, 10, 1, 3},
            {-4, -1, 1, 7, -6}
        };

        System.out.println("最大子矩阵和为: " + maxSumRectangle(matrix)); // 输出: 29
    }
}

代码运行详解

输入矩阵：

[
    [1,  2, -1, -4, -20],
    [-8, -3, 4,  2,   1],
    [3,   8, 10, 1,   3],
    [-4, -1, 1,  7,  -6]
]

步骤 1：固定左右边界

左边界 l = 0，右边界 r = 0：
- 列累积和 temp = [1, -8, 3, -4]
- 使用 Kadane 算法找到最大子数组和为 3，对应上下边界 [2, 2]。
左边界 l = 0，右边界 r = 1：
- 列累积和 temp = [3, -11, 11, -5]
- 最大子数组和为 11，对应上下边界 [2, 2]。
左边界 l = 1，右边界 r = 3：
- 列累积和 temp = [1, 3, 15, 4]
- 最大子数组和为 29，对应上下边界 [1, 2]。