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