在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值 输入描述: 每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D : 3 <= N <= 100 1 <= D <= N 接下来有N行，每行N个数字d: 0 <= d <= 100
输出描述: 输出一个整数，表示找到的和的最大值
输入例子: 4 2 87 98 79 61 10 27 95 70 20 64 73 29 71 65 15 0
输出例子: 193
思路：题目要求求出所有横向，竖向和对角线D个连续数字的最大值。
最简单的方法：分别求出横(horizon)，竖(vertical)，左上到右下(left_top)，左下到右上(right_top)的值，取其中最大的一个。
一开始解题的时候我想着在两个for循环中直接求出以上四个值，后面发现这不是明智之举，因为，代码一多思维就乱，总是不能通过所有测试。后面索性一个一个求，一开始肯定超时，后面经过优化AC掉了.
Ac代码：
import java.util.List;import java.util.Scanner;public class TowSum { public static void main(String args[]) { Scanner in = new Scanner(System.in); while (in.hasNext()) {// 注意while处理多个case int n = in.nextInt(); int d = in.nextInt(); int[][] awarry = new int[n][n];// 初始化数组 for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { awarry[x][y] = in.nextInt(); } } System.out.PRintln(test(n, d, awarry)); } } public static int getMax(int startX, int startY, int length, int[][] num) { int result = 0; int left_top = 0; int right_top = 0; int horizon = 0; int vertical = 0; for (int x = startX, y = startY, y2 = startY + length - 1; x < startX + length; x++, y++,y2--) { left_top += num[x][y]; right_top += num[x][y2]; } for (int i = startX; i < startX + length; i++) { int local_vertical = 0; for (int j = startY; j < startY + length; j++) { local_vertical += num[i][j]; } vertical = Math.max(local_vertical, vertical); } for (int y = startY; y < startY + length; y++) { int local_honrizon = 0; for (int x = startX; x < startX + length; x++) { local_honrizon += num[x][y]; } horizon = Math.max(local_honrizon, horizon); } result = Math.max(Math.max(left_top, right_top), Math.max(vertical, horizon)); return result; } public static int test(int N, int D, int[][] num) { int result = 0; for (int i = 0; i <= N - D; i++) { for (int j = 0; j <= N - D; j++) { result = Math.max(result, getMax(i, j, D, num)); } } return result; }}新闻热点
疑难解答
