| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Java解决方案import java.util.Scanner;
/**
* @author Wanghs
* @create 2022/3/10
* @description
*/
public class Main{
private static int[][] sum; //s(i,j)代表以第i行第j个元素为起始,垂直长度为row+1的列的和。
private static int[][] arr; //存储二维数组
private static int n; //存储二维数组的边长
private static int totalMax = -12800; //存储最终结果
private static void findMax() {
int[] rowP = new int[n]; //动态规划序列
int[] rowA = new int[n]; //放置当前操作行
for (int row = 0; row < n; row++) {
for (int i = 0; i < (n - row); i++) {
rowA = arr[row + i];
for (int j = 0; j < n; j++) {
sum[row][j] += rowA[j];
}
rowP[0] = sum[row][0]; //问题转化成,在这个行中,求最大字段和的问题
for (int j = 1; j < n; j++) { //一维最大子序列和的问题
if (rowP[j - 1] < 0) {
rowP[j] = sum[row][j];
} else {
rowP[j] = rowP[j - 1] + sum[row][j];
}
}
int max = -12800;
for (int j = 0; j < n; j++) {
if (rowP[j] > max) {
max = rowP[j]; //求出的max就是在垂直长度为row+1的所有矩形中,矩形内元素和的最大值
}
}
if (totalMax < max) {
totalMax = max; //最终结果
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n][n];
sum = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = scan.nextInt();
}
}
findMax();
System.out.println(totalMax);
scan.close();
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator