最大子矩阵

/*
 * 思路：
 * 使用动态规划和Kadane算法来解决这个问题。
 * 这里使用Java Stream API实现。
 * 首先，将每一列的元素累加起来，然后使用Kadane算法在累加数组上找出最大子数组和。
 * 在找出最大子数组和的同时，记录对应的行索引。
 * 最后，通过累加的列索引和Kadane算法得到的行索引确定最大子矩阵的左上角和右下角。
 */

import java.util.stream.IntStream;

public class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[] result = new int[4];
        int maxSum = Integer.MIN_VALUE;
        
        for (int left = 0; left < col; left++) {
            int[] rowSum = new int[row];
            for (int right = left; right < col; right++) {
                IntStream.range(0, row).forEach(i -> rowSum[i] += matrix[i][right]);
                int[] tempResult = kadane(rowSum);
                if (tempResult[2] > maxSum) {
                    maxSum = tempResult[2];
                    result[0] = tempResult[0];
                    result[1] = left;
                    result[2] = tempResult[1];
                    result[3] = right;
                }
            }
        }
        return result;
    }
    
    private int[] kadane(int[] array) {
        int start = 0, end = 0, tempStart = 0, maxSum = array[0], sum = array[0];
        for (int i = 1; i < array.length; i++) {
            if (sum < 0) {
                sum = array[i];
                tempStart = i;
            } else {
                sum += array[i];
            }
            if (sum > maxSum) {
                maxSum = sum;
                start = tempStart;
                end = i;
            }
        }
        return new int[] {start, end, maxSum};
    }
}