我要招人

去企业版

首页 > 试题广场 >

最大和

[编程题]最大和

热度指数：6225 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值

输入描述:

每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D :
3 <= N <= 100
1 <= D <= N
接下来有N行，每行N个数字d:
0 <= d <= 100

输出描述:

输出一个整数，表示找到的和的最大值

示例1

输入

4 2
87 98 79 61
10 27 95 70
20 64 73 29
71 65 15 0

输出

算法知识视频讲解

Java

AA应SL

import java.util.Scanner;

public class test2 {

public static void main(String args[]){

Scanner s=new Scanner(System.in);

int n;

int d;

int mm=0;

int mm2=0;

int max1=0;

int max2=0;

int max3=0;

int max4=0;

n= s.nextInt();

d= s.nextInt();

int[][] a1=new int[n][n];

for(int i=0;i<n;i++){

for(int j=0;j<n;j++){

a1[i][j]=s.nextInt();

}

for(int i=0;i<n;i++){

for(int j=0;j<=n-d;j++){

for(int k=0;k<d;k++){

max1=max1+a1[i][j+k];//横向

max2=max2+a1[j+k][i];//纵向

}

if(max1>max2){

if(max1>mm){mm=max1;}

}else if(max2>mm){

mm=max2;

}

max1=0;

max2=0;

}

for(int i=0;i<=n-d;i++){

for(int j=0;j<=n-d;j++){

for(int k=0;k<d;k++){

max3=max3+a1[i+k][j+k];//左上右下

max4=max4+a1[i+k][n-j-k-1];//右上左下

}

if(max3>max4){

if(max3>mm2){mm2=max3;}

}else if(max4>mm2){mm2=max4;}

max3=0;

max4=0;

}

if(mm>mm2){mm2=mm;}

System.out.print(mm2);

}

发表于 2017-03-08 11:24:21 回复(0)

Java

我爱烦事

import java.util.Scanner;
public class Main{ 
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
        int N = 0;
        int D = 0;
        N = scan.nextInt();
        D = scan.nextInt();
        int[][] nums = new int[N][N];
        for(int i = 0; i < N; i++){
        	for(int j = 0; j < N; j++){
        		nums[i][j] = scan.nextInt();
        	}
        }
        int max = 0;
        
        //确定各方向的第一个值的索引
        for(int k = 0; k < N; k++){
        	//确定各方向连续D个值的开始索引
            for(int begin = 0; begin <= N-D; begin++){
            	//横
            	int hsum = 0;
            	//竖
            	int ssum = 0;
            	//左上到右下1
            	int lsum1 = 0;
            	//左上到右下2
            	int lsum2 = 0;
            	//右上到左下1
            	int rsum1 = 0;
            	//右上到左下2
            	int rsum2 = 0;
            	//开始求各方向连续D个数的和
            	for(int m = 0; m < D; m++){
            		hsum += nums[k][begin+m];
            		ssum += nums[begin+m][k];
            		if((k+D+begin) <= N){
            			lsum1 += nums[k+begin+m][begin+m];
            			//避免1和2重复求k=0时的和
            			if(k != 0){
            				lsum2 += nums[begin+m][k+begin+m];
            				rsum2 += nums[k+begin+m][N-1-begin-m];
            			}
            		}
            		if((N-k-begin-D) >= 0){
            			rsum1 += nums[m+begin][N-1-k-begin-m];
            		}
            	}
            	if(hsum > max)
            		max = hsum;
            	if(ssum > max)
            		max = ssum;
            	if(lsum1> max)
            		max = lsum1;
            	if(lsum2 > max)
            		max = lsum2;
            	if(rsum1 > max)
            		max = rsum1;
            	if(rsum2 > max)
            		max = rsum2;
            }
        }
        System.out.println(max);
	}
}

编辑于 2017-03-07 23:55:35 回复(2)

Java

YuanS

import java.awt.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; /**  * Created by Yuan on 2017/3/1.  */ public class Main { public static void main(String[] args) throws IOException {
        Scanner scanner=new Scanner(System.in); int N= scanner.nextInt(); int D=scanner.nextInt(); int[][] Datas=new int[N][N]; for (int i=0;i<N;i++){ for (int j=0;j<N;j++){
               Datas[i][j]=scanner.nextInt();
            }
        } int maxValue=0; //水平查找和垂直查找  for (int i=0;i<N;i++){ for (int j=0;j<N-D+1;j++){ int sumLevel=0; int sumHigh=0; for (int k=0;k<D;k++){
                    sumLevel=sumLevel+Datas[i][j+k];
                    sumHigh=sumHigh+Datas[j+k][i];
                } int temp; if (sumHigh>sumLevel) temp=sumHigh;else temp=sumLevel; if (temp>maxValue){
                    maxValue=temp;
                }

            }
        } //斜直线查找,讲两次斜线查找看作N-D*N-D的矩阵，分别从左上和右上开始计算  for (int i=0;i<N-D+1;i++){ for (int j=0;j<N-D+1;j++){ int sumL=0; int sumR=0; for (int k=0;k<D;k++){
                    sumR=Datas[i+k][N-j-1-k]+sumR;
                    sumL=Datas[i+k][j+k]+sumL;
                } int temp; if (sumR>sumL) temp=sumR;else temp=sumL; if (temp>maxValue) maxValue=temp;
            }
        }

        System.out.println(maxValue);

    }
}