最大的和
題目來源：《資訊學奧賽一本通》
時間限制：\(1000ms\) 記憶體限制：\(64mb\)
題目描述
給定一個包含整數的二維矩陣，子矩形是位于整個陣列內的任何大小為 \(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 * N\) 的整數陣列，
第一行只輸入一個整數 \(N\) ，表示方形二維陣列的大小，
從第二行開始，輸入由空格和換行符隔開的 \(N^2\) 個整數，它們即為二維陣列中的 \(N^2\) 個元素，輸入順序從二維陣列的第一行開始向下逐行輸入，同一行資料從左向右逐個輸入，
陣列中的數字會保持在 \([-127,127]\) 的范圍內，
輸出格式
輸出一個整數，代表最大子矩形的總和，
資料范圍
\(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);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/254727.html
標籤：其他