2021冬休み毎日1題『最大の和』

最大和
テーマ出所:《情報学奥赛一本通》時間制限:1000 m s 1000 ms 1000 msメモリ制限:64 m b 64 mb 64 mb
タイトルの説明
整数を含む2次元行列が与えられ、サブ矩形は、アレイ全体に位置する任意のサイズ1×1×1×1以上の連続サブアレイである.長方形の合計は、長方形内のすべての要素の合計です.この問題では,最大和を持つサブ矩形を最大サブ矩形と呼ぶ.
たとえば、次の配列があります.

 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2

最大サブ長方形:

 9  2
-4  1
-1  8

最大15を所有しています.
入力フォーマット
入力には、N最初の行には、正方形の2次元配列のサイズを表す整数N N Nのみが入力されます.2行目から、スペースと改行で区切られたN 2 N^2 N 2個の整数、すなわち2次元配列のN 2 N^2 N 2個の要素を入力し、入力順は2次元配列の1行目から下へ、同じ行のデータを左から右へ入力します.配列内の数字は［−127,127］［−127127］［−127127］の範囲内に保持される.
出力フォーマット
最大サブ長方形の合計を表す整数を出力します.
データ範囲
1 ≤ N ≤ 100 1 ≤ N ≤ 100 1≤N≤100
サンプル入力

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

サンプル出力

15

問題を解く構想.
AcWing 126. 最大の和:Tell_me
解題コード-Java

import java.util.Scanner;

public class Main {
     
    public static void main(String[] args) {
     
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[][] array = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
     
            for (int j = 1; j <= n; j++) {
     
                array[i][j] = input.nextInt();
                array[i][j] += array[i - 1][j];
            }
        }
        input.close();

        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
     
            for (int j = i; j <= n; j++) {
     
                int last = 0;
                for (int k = 1; k <= n; k++) {
     
                    last = Math.max(last, 0) + array[j][k] - array[i - 1][k];
                    ans = Math.max(ans, last);
                }
            }
        }

        System.out.println(ans);
    }
}