课堂作业——返回最大子矩阵

package com.Cra2iTeT;

import java.util.Scanner;

/**
 * @author Cra2iTeT
 * @version 1.0
 * @date 2022/3/18 9:54
 */
public class Lesson02_test02 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int row = 0;
        int col = 0;

        row = scanner.nextInt();
        col = scanner.nextInt();

        int temp = 0;
        int max = 0;

        int[][] tempInt = new int[row + 1][col + 1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                tempInt[i][j] = tempInt[i - 1][j] + scanner.nextInt();      //这种办法每个位置存储的是该列从第一行加到此行的和
//                System.out.print(tempInt[i][j]+"\t");
            }
//            System.out.println();
        }

        temp = max = tempInt[1][1];     //初始化数据，这种初始化可以避免最大值出现在第一位同时全是负数的结果最大值为0的情况

        /*
         * 这里其实就是一种遍历，数组是从1开始记录的，最内层循环第一次记录该列从第一行加到此的和，如果大就记录下来
         * 最内层第二次循环计算的是该列从第二行加到此的和，如果更大就替换最值，以此类推
         * 同时如果和小于0，说明前面的数据对后续没有帮助，直接舍弃
         * */
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= i; j++) {      //这里代码看着很抽象，回归到原问题，我们要求的是子矩阵，把这一层循环嵌套想成是求上三角或者下三角会好理解一些
                temp = 0;
                for (int k = 1; k <= col; k++) {
                    temp = tempInt[i][k] - tempInt[j - 1][k] + temp;

                    if (temp > max) {
                        max = temp;
                    }
                    if (temp < 0) {
                        temp = 0;
                    }
                }
            }
        }

        System.out.println(max);
    }
}

想到了使用暴力算法，不过我个人的思路是按整行计算过去，然后再考虑最大和。但是自己也嫌这种方法麻烦。

中午休息的时候恰好看到一篇文章：https://blog.csdn.net/tianjindong0804/article/details/79241570?utm_source=app&app_version=5.1.0

总体思路是一致的，都是暴力解，但是他采用的是按列计算，数组存储和后续循环遍历的时候比我更巧，所以就用了他的解法。但是原文没有过多解释，我就添加了一些自己的见解。