[编程题]最大和
- 热度指数：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
输出
193
#include<iostream>
#include<string>
using namespace std;
int maps[105][105];
int map1[105][105];
int map2[105][105];
int map3[105][105];
int map4[105][105];
/*初始化四个数组，分别表示水平相加，竖直相加，主对角线，次对角线
对于水平相加的数组，a[i][j]表示第i行前j个元素相加，竖直相加的数组类似
对于主对角线的数组，a[i][j]表示第i行第j列所在的元素所在的对角线的叠加，次对角线类似
这样做是在计算的时候减少了一层循环，减少时间复杂度
*/
void init(int n){
///水平相加
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map1[i][j]=map1[i][j-1]+maps[i][j];
}
}
///竖直相加
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map2[i][j]=map2[i-1][j]+maps[i][j];
}
}
///主对角线相加
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map3[i][j]=map3[i-1][j-1]+maps[i][j];
}
}
///次对角线相加
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--){
map4[i][j]=map4[i-1][j+1]+maps[i][j];
}
}
}
int main()
{
int N,D;
cin>>N>>D;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cin>>maps[i][j];
}
}
init(N);
int ans=0;
int r1,r2,r3,r4;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
r1=r2=r3=r4=0;
if(j>=D){
r1=map1[i][j]-map1[i][j-D];
}
if(i>=D){
r2=map2[i][j]-map2[i-D][j];
}
if(i>=D&&j>=D){
r3=map3[i][j]-map3[i-D][j-D];
///这里次对角线的处理，比较特殊，需要对于j向后平移一个
r4=map4[i][j-D+1]-map4[i-D][j+1];
}
ans=max(ans,max(max(r1,r2),max(r3,r4)));
}
}
cout<<ans<<endl;
return 0;
}
发表于 2018-07-11 13:39:49
回复(0)
更多回答
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)
#include<iostream>
#include<cmath>
using namespace std;
struct sum_struct{
int sum_left;
int sum_left_top;
int sum_top;
int sum_right_top;
sum_struct(){
sum_left=0;
sum_left_top=0;
sum_top=0;
sum_right_top=0;
}
};
int max_func(int a, int b){
return a>b?a:b;
}
int main(){
int m,n;
while(cin>>m>>n){
// zero padding to deal with edge situations
sum_struct st[102*102];
int max_sum=0, num;
for(int i=0;i<m*m;i++){
cin>>num;
int row = floor(i/m);
int col = i%m;
int offset_i = (m+2)*(row+1)+(col+1);
// update sum
st[offset_i].sum_left = num +
st[offset_i-1].sum_left;
st[offset_i].sum_top = num +
st[offset_i-(m+2)].sum_top;
st[offset_i].sum_left_top = num +
st[offset_i-(m+2)-1].sum_left_top;
st[offset_i].sum_right_top = num +
st[offset_i-(m+2)+1].sum_right_top;
// update max
if(col>=n-1)
max_sum = max_func(max_sum, st[offset_i].sum_left
- st[offset_i-n].sum_left);
if(row>=n-1)
max_sum = max_func(max_sum, st[offset_i].sum_top
- st[offset_i-(m+2)*n].sum_top);
if(col>=n-1 && row>=n-1)
max_sum = max_func(max_sum,
st[offset_i].sum_left_top - st[offset_i-(m+2)*n-n].sum_left_top);
if(col<=m-n && row>=n-1)
max_sum = max_func(max_sum,
st[offset_i].sum_right_top - st[offset_i-(m+2)*n+n].sum_right_top);
}
cout<<max_sum<<endl;
}
return 0;
}
编辑于 2017-03-07 12:00:14
回复(1)
分别判断横、竖、左斜右斜，思路很简单，就是方位要找好，debug比较麻烦；
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int d=in.nextInt();
int a[][]=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j]=in.nextInt();
}
}
int max1=Math.max(heng(a,n,d),shu(a,n,d));
int max2=Math.max(zuoxie(a,n,d),youxie(a,n,d));
System.out.println(Math.max(max1,max2));
}
static int heng(int[][] a,int n,int d){
int max=0;
for(int j=0;j<n;j++){
int l=0,r=d-1;int sum=0;
for(int i=0;i<d;i++){
sum+=a[j][i];
}
max=Math.max(sum,max);
while(r+1<n){
max=Math.max(max,sum+a[j][++r]-a[j][l]);sum+=a[j][r]-a[j][l];l++;
}
}
return max;
}
static int shu(int[][] a,int n,int d){
int max=0;
for(int j=0;j<n;j++){
int l=0,r=d-1;int sum=0;
for(int i=0;i<d;i++){
sum+=a[i][j];
}
max=Math.max(sum,max);
while(r+1<n){
max=Math.max(max,sum+a[++r][j]-a[l][j]);sum+=a[r][j]-a[l][j];l++;
}
}
return max;
}
static int zuoxie(int[][] a,int n,int d){
int max=0;
for(int j=0;j<=n-d;j++){
int l1=j,l2=0,r1=j,r2=0;int sum=0;
for(;r2<d;r2++,r1++){
sum+=a[r1][r2];
}
r2--;r1--;
max=Math.max(sum,max);
while(r1+1<n){
max=Math.max(max,sum+a[++r1][++r2]-a[l1][l2]);sum+=a[r1][r2]-a[l1][l2];l1++;l2++;
}
}
for(int j=1;j<=n-d;j++){
int l1=0,l2=j,r1=0,r2=j;int sum=0;
for(;r1<d;r2++,r1++){
sum+=a[r1][r2];
}
r2--;r1--;
max=Math.max(sum,max);
while(r2+1<n){
max=Math.max(max,sum+a[++r1][++r2]-a[l1][l2]);sum+=a[r1][r2]-a[l1][l2];l1++;l2++;
}
}
return max;
}
static int youxie(int[][] a,int n,int d){
int max=0;
for(int j=d-1;j<n;j++){
int l1=j,l2=0,r1=j,r2=0;int sum=0;
for(;r2<d;r2++,r1--){
sum+=a[r1][r2];
}
r2--;r1++;
max=Math.max(sum,max);
while(r1-1>=0){
max=Math.max(max,sum+a[--r1][++r2]-a[l1][l2]);sum+=a[r1][r2]-a[l1][l2];l1--;l2++;
}
}
for(int j=1;j<=n-d;j++){
int l1=n-1,l2=j,r1=n-1,r2=j;int sum=0;
for(;r1>=n-d;r2++,r1--){
sum+=a[r1][r2];
}
r2--;r1++;
max=Math.max(sum,max);
while(r2+1<n){
max=Math.max(max,sum+a[--r1][++r2]-a[l1][l2]);sum+=a[r1][r2]-a[l1][l2];l1--;l2++;
}
}
return max;
}
}
发表于 2022-03-25 23:52:06
回复(0)
| #include<iostream> usingnamespacestd; intmain() { intjie, num, array[10][10], k = 0; cin >> jie >> num; intright, low; intcount, out[100] = {0}; for(inti = 0; i < jie; ++i) { for(intj = 0; j < jie; ++j) { right = jie - i - num; low = jie - j - num; count = 0; if(right >= 0 && low >= 0) { while(num--) { count += array[i+num-1][j+num-1]; } out[k++] = count; } count = 0; if(right >= 0 && low < 0) { while(num--) { count += array[i][j + num - 1]; } out[k++] = count; } count = 0; if(right < 0 && low >= 0) { while(num--) { count += array[i+num-1][j]; } out[k++] = count; } } } intmax = out[0]; for(intm = 1; m < k; ++m) { if(out[m] > max) { max = out[m]; } } cout << max; return0; } |
- 我这个代码出现了段错误，请大佬解答（里面缺少的一种情况先忽略不计），小妹不胜感谢。
发表于 2019-08-29 14:38:42
回复(0)
//维护四个前缀和
#include <cstdio>
#include <cstring>
#include <algorithm>
usingnamespacestd;
intn, d, a[110][110], srow[110][110], scol[110][110], srd[110][110], sld[110][110];
intmain() {
scanf("%d%d", &n, &d);
for(inti = 1; i <= n; i++)
for(intj = 1; j <= n; j++)
scanf("%d", &a[i][j]);
for(inti = 1; i <= n; i++)
for(intj = 1; j <= n; j++) {
srow[i][j] = srow[i][j-1] + a[i][j];
scol[j][i] = scol[j][i-1] + a[i][j];
srd[i][j] = srd[i-1][j-1] + a[i][j];
sld[i][j] = sld[i-1][j+1] + a[i][j];
}
intans = 0;
for(inti = 1; i <= n; i++)
for(intj = 1; j <= n; j++) {
intli = i - d, lj = j - d, rj = j+d;
if(lj >= 0)
ans = max(ans, srow[i][j] - srow[i][lj]);
if(li >= 0)
ans = max(ans, scol[j][i] - scol[j][li]);
if(li >= 0 && lj >= 0)
ans = max(ans, srd[i][j] - srd[li][lj]);
if(li >= 0 && rj <= n+1)
ans = max(ans, sld[i][j] - sld[li][rj]);
}
printf("%d\n", ans);
return0;
}
发表于 2019-03-08 16:46:47
回复(1)
#include <bits/stdc++.h>usingnamespacestd;intrl( vector<vector<int> > dp, intN, intD){intres = 0;for(inti = 0; i<N; i++){for(intj = 0; j<N-D+1; j++){inttmp = 0;for(intt = 0; t<D; t++){tmp += dp[i][j + t];}res = max(res, tmp);}}returnres;}inttb( vector<vector<int> > dp, intN, intD){intres = 0;for(inti = 0; i<N-D+1; i++){for(intj = 0; j<N; j++){inttmp = 0;for(intt = 0; t<D; t++){tmp += dp[i+t][j];}res = max(res, tmp);}}returnres;}intrl1( vector<vector<int> > dp, intN, intD){intres = 0;for(inti = 0; i<N-D+1; i++){for(intj = 0; j<N-D+1; j++){inttmp = 0;for(intt = 0; t<D; t++){tmp += dp[i+t][j + t];}res = max(res, tmp);}}returnres;}inttb1(vector<vector<int> > dp, intN, intD){intres = 0;for(inti = 0; i < N-D +1; i++){for(intj = N-1; j >= D -1; j--){inttmp = 0;for(intt = 0; t<D; t++){tmp += dp[i + t][j - t];}res = max(res, tmp);}}returnres;}intmain(){intN,D;while(cin>>N>>D){vector<vector<int> > dp;vector<int> v;intd;for(inti=0;i<N;i++){v.clear();for(intj=0;j<N;j++){cin>>d;v.push_back(d);}dp.push_back(v);}intmax1=rl(dp,N,D);intmax2=tb(dp,N,D);intmax3=rl1(dp,N,D);intmax4=tb1(dp,N,D);intres =max(max(max(max1,max2),max3),max4);cout<<res<<endl;}return0;}
发表于 2018-08-09 16:39:22
回复(0)
//为什么用java写的人辣么少呢，，，
//这个感觉不是很难，就是有点复杂代码。。。
import java.util.Scanner;
/**
* Created by huali on 2018/5/25.
*/
public class Main {
// 在一个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
//
//输出例子1:
//193
public static void main(String []args)
{
Scanner sr = new Scanner(System.in);
while (sr.hasNext())
{
int N = sr.nextInt();
int D = sr.nextInt();
int [][]arr = new int[N][N];
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
arr[i][j] = sr.nextInt();
}
}
int max= 0;
for (int i = 0; i < N; ++i)
{
for (int start = 0; start <= N-D; ++start)
{
int sum=0;
for (int k = 0; k < D; ++k)
{
sum+=arr[i][start+k];
}
max = Math.max(max, sum);
}
}
for (int i = 0; i < N; ++i)
{
for (int start = 0; start <= N-D; ++start)
{
int sum=0;
for (int k = 0; k < D; ++k)
{
sum+=arr[start+k][i];
}
max = Math.max(max, sum);
}
}
for(int i=0;i<N;i++)
{
//按照列
for(int j=0;j<N;j++)
{
int temp = 0;
if(i+D-1>=0&&i+D-1<N&&j-D+1>=0&&j-D+1<N)
{
for (int k = 0; k < D; ++k)
{
temp += arr[i+k][j-k];
}
max = Math.max(max, temp);
}
}
//max = Math.max(max, temp);
}
for(int i=0;i<N;i++)
{
//按照列
//int temp = 0;
for(int j=0;j<N;j++)
{
int temp = 0;
if(i+D-1>=0&&i+D-1<N&&j+D-1>=0&&j+D-1<N)
{
for (int k = 0; k < D; ++k)
{
temp += arr[i+k][j+k];
}
max = Math.max(max, temp);
}
}
//max = Math.max(max, temp);
}
System.out.println(max);
}
sr.close();
}
}
编辑于 2018-05-25 21:04:00
回复(0)
//使用积分图加快运算
#include <iostream>
#include <vector>#include <numeric>
#include <limits>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;
static int maxsum = -2147483647;
void inpudata(vector<vector<int>> &input,const int N) {
int tmp;
vector<int> tmpvec;
for (int i = 0; i < N; i++) {
tmpvec.clear();
for (int j = 0; j < N; j++) {
cin >> tmp;
tmpvec.push_back(tmp);
}
input.push_back(tmpvec);
}
}
void rowMax(const vector<vector<int>> &input,const int D,const int N) {
int tmpsum;
for (int i = 0; i < N; i++) {
tmpsum = 0;
for (int j = 0; j < D; j++) {
tmpsum += input[i][j];
}
if (tmpsum > maxsum) {
maxsum = tmpsum;
}
for (int j = D; j < N; j++) {
tmpsum -= input[i][j - D];
tmpsum += input[i][j];
if (tmpsum > maxsum) {
maxsum = tmpsum;
}
}
}
}
void colMax(const vector<vector<int>> &input, const int D, const int N) {
int tmpsum;
for (int i = 0; i < N; i++) {
tmpsum = 0;
for (int j = 0; j < D; j++) {
tmpsum += input[j][i];
}
if (tmpsum > maxsum) {
maxsum = tmpsum;
}
for (int j = D; j < N; j++) {
tmpsum -= input[j-D][i];
tmpsum += input[j][i];
if (tmpsum > maxsum) {
maxsum = tmpsum;
}
}
}
}
void upleftTobottomrightMax(const vector<vector<int>> &input, const int D, const int N) {
vector<vector<int>> summap;
vector<int> sumvec(N+1,0);
summap.push_back(sumvec);
int tmpsum;
for (int i = 0; i < N; i++) {
sumvec.clear();
sumvec.push_back(0);
for (int j = 1; j <=N; j++) {
sumvec.push_back(summap[i][j - 1] + input[i][j-1]);
}
summap.push_back(sumvec);
}
for (int i = D - 1; i < N; i++) {
for (int j = D - 1; j < N; j++) {
tmpsum = summap[i+1][j+1] - summap[i - D +1][j - D + 1];
if (tmpsum> maxsum) {
maxsum = tmpsum;
}
}
}
}
void uprightTobottomleftMax(const vector<vector<int>> &input, const int D, const int N) {
vector<vector<int>> summap;
vector<int> sumvec(N + 1, 0);
summap.push_back(sumvec);
int tmpsum;
for (int i = 0; i < N; i++) {
vector<int> sumvec2(N + 1, 0);
for (int j = N-1; j >=0; j--) {
sumvec2[j]=summap[i][j+1]+input[i][j];
}
summap.push_back(sumvec2);
}
for (int i = D-1; i <N; i++) {
for (int j = 0; j < N-D+1; j++) {
tmpsum = summap[i + 1][j] - summap[i - D +1][j+D];
if (tmpsum> maxsum) {
maxsum = tmpsum;
}
}
}
}
int main() {
vector<vector<int>> input;
int N, D;
cin >> N;
cin >> D;
inpudata(input, N);
uprightTobottomleftMax(input, D, N);
rowMax(input,D,N);
upleftTobottomrightMax(input,D,N);
colMax(input, D, N);
cout<<maxsum<<endl;
return 0;
}
发表于 2018-03-11 18:50:24
回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main()
{
using namespace std;
int n, d;
while (cin >> n >> d) {
vector<vector<int> > matrix(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> matrix[i][j];
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n - d; j++) {
int ret = 0;
for (int k = j; k < j + d; k++) {
ret += matrix[i][k];
}
if (ret > ans)
ans = ret;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n - d; j++) {
int ret = 0;
for (int k = j; k < j + d; k++) {
ret += matrix[k][i];
}
if (ret > ans)
ans = ret;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int ret = 0;
for (int k = 0; k < d; k++) {
if (i + k >= n || j + k >= n)
break;
ret += matrix[i + k][j + k];
}
if (ret > ans)
ans = ret;
}
}
for (int i = 0; i < n - d + 1; i++) {
for (int j = n - 1; j >= 0; j--) {
int ret = 0;
for (int k = 0; k < d; k++) {
if (i + k >= n || j - k < 0)
break;
ret += matrix[i + k][j - k];
}
if (ret > ans) {
ans = ret;
}
}
}
cout << ans << endl;
}
return 0;
}
发表于 2017-04-26 16:22:21
回复(0)
#include <iostream>#include <string> using namespace std; int main() { int n, d, a[101][101]; scanf("%d%d", &n, &d); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &a[i][j]); } } int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int temp; if (n - j >= d) { //横 temp = 0; for (int k = j; k < j + d; ++k) { temp += a[i][k]; } ans = max(temp, ans); } if (n - i >= d) { //竖 temp = 0; for (int k = i; k < i + d; ++k) { temp += a[k][j]; } ans = max(ans, temp); } if (n - i >= d && n - j >= d) { //左上到右下 temp = 0; for (int k = i, l = j; k < i + d, l < j + d; ++k, ++l) { temp += a[k][l]; } ans = max(ans, temp); } if (n - i >= d && j >= d - 1) { //右上到左下 temp = 0; for (int k = i, l = j; k < i + d, l > j - d; ++k, --l) { temp += a[k][l]; } ans = max(ans, temp); } } } cout << ans << endl; return 0; }
编辑于 2017-03-19 21:54:21
回复(0)
卡最后一个案例 的注意题意 ，连续的D个数，也就是不包括小于D个数的答案， 当然讲道理D个数的和
大于D-1 个数的和，算不算都无所谓，但是不包括有负数的情况，所以会出现极端情况，D-1个数的
和大于D个数和，所以避免计算小于D个数的和，这样不会卡最后一个案例
#include<bits/stdc++.h>
using namespace std;
const int N=100;
int arr[N][N];
int main()
{
int i,j,k;
int n,d;
int sum=0;
int ans[N][N];
cin>>n>>d;
for(i=0; i<n; i++){
for(j=0; j<n; j++){
cin>>arr[i][j];
}
}
int m1 = 0;//横行
for(i=0; i<n; i++){
for(j=0; j<n; j++){
sum = 0;
for(k=0; k<d; k++){
if(j+k>=n) break;
sum += arr[i][j+k];
}
if(m1 < sum){
m1 = sum;
}
}
}
//cout<<m1<<endl;
int m2=0; //竖列
for(i=0; i<n; i++){
for(j=0; j<n; j++){
sum = 0;
for(k=0; k<d; k++){
if(j+k>=n) break;
sum += arr[j+k][i];
}
if(m2 < sum){
m2 = sum;
}
}
}
//cout<<m2<<endl;
int m3=0; //左上到右下
for(i=0; i<n; i++){
for(j=0; j<n; j++){
sum = 0;
for(k=0; k<d; k++){
if(i+k>= n || j+k >= n) break;
sum += arr[i+k][j+k];
}
if(m3<sum){
m3 = sum;
}
}
}
//cout<<m3<<endl;
int m4=0; //右上到左下
for(i=0; i<n-d+1; i++){
for(j=n-1; j>=0; j--){
sum = 0;
for(k=0; k<d; k++){
if(i+k>=n || j-k<0 ) break;
sum += arr[i+k][j-k];
}
//cout<<sum<<" ";
if(m4<sum){
m4 = sum;
}
}
}
//cout<<m4<<endl;
int ma=0;
ma = max(ma,m1);
ma = max(ma,m2);
ma = max(ma,m3);
ma = max(ma,m4);
cout<<ma<<endl;
return 0;
}
发表于 2017-03-16 18:30:41
回复(14)
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)
import java.io.*;
public class Main {
public static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
static int res = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] row1 = br.readLine().trim().split(" ");
int N = Integer.parseInt(row1[0]);
int D = Integer.parseInt(row1[1]);
int[][] grid = new int[N][N];
for (int i = 0; i < N; i++) {
String[] temp = br.readLine().trim().split(" ");
for (int j = 0; j < N; j++) {
grid[i][j] = Integer.parseInt(temp[j]);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res = Math.max(res, dfs(grid, i, j, D, N));
}
}
System.out.println(res);
br.close();
}
public static int dfs(int[][] grid, int i, int j, int D, int N) {
int ans = grid[i][j];
int cur = ans; //当前层的初值
D--;
if (D == 0) return ans;
for (int[] info : DIRECTIONS) {
int newX = i + info[0];
int newY = j + info[1];
if (isArea(newX, newY, N)) {
cur += dfs(grid, newX, newY, D, N);
ans = Math.max(ans, cur);
}
}
return ans;
}
public static boolean isArea(int i, int j, int N) {
return i >= 0 && i < N && j >= 0 && j < N;
}
public class Main {
public static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
static int res = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] row1 = br.readLine().trim().split(" ");
int N = Integer.parseInt(row1[0]);
int D = Integer.parseInt(row1[1]);
int[][] grid = new int[N][N];
for (int i = 0; i < N; i++) {
String[] temp = br.readLine().trim().split(" ");
for (int j = 0; j < N; j++) {
grid[i][j] = Integer.parseInt(temp[j]);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res = Math.max(res, dfs(grid, i, j, D, N));
}
}
System.out.println(res);
br.close();
}
public static int dfs(int[][] grid, int i, int j, int D, int N) {
int ans = grid[i][j];
int cur = ans; //当前层的初值
D--;
if (D == 0) return ans;
for (int[] info : DIRECTIONS) {
int newX = i + info[0];
int newY = j + info[1];
if (isArea(newX, newY, N)) {
cur += dfs(grid, newX, newY, D, N);
ans = Math.max(ans, cur);
}
}
return ans;
}
public static boolean isArea(int i, int j, int N) {
return i >= 0 && i < N && j >= 0 && j < N;
}
}
家人们帮我看看，为什么我的爆搜就过了5个用例就超时了
发表于 2022-08-12 16:36:11
回复(0)
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int d = input.nextInt();
int arr[][] = new int[n][n];
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
arr[x][y] = input.nextInt();
}
}
int max = 0;
//从每个点出发，都有四种可能，到左下角的和、到右下角的和、下垂直方向的和、右水平方向的和
//每次计算完这四个方向的和，就让top指针自增，即向右移动到下一个，该行全部计算完后，再让left下移到下一行，同时top从0开始计算
for (int left = 0; left < n; left++) {
for (int top = 0; top < n; top++) {
if (top + 1 - d >= 0 && left - 1 + d < n) {
int temp = leftLine(arr, left, top, d);
max = max > temp ? max : temp;
}
if (top - 1 + d < n && left - 1 + d < n) {
int temp = rightLine(arr, left, top, d);
max = max > temp ? max : temp;
}
if (top - 1 + d < n) {
int temp = horizontalLine(arr, left, top, d);
max = max > temp ? max : temp;
}
if (left - 1 + d < n) {
int temp = verticalLine(arr, left, top, d);
max = max > temp ? max : temp;
}
}
}
System.out.println(max);
}
static int leftLine(int[][] arr, int left, int top, int d) {
int result = 0;
for (int x = 0; x < d; x++) {
result += arr[left][top];
left++;
top--;
}
return result;
}
static int rightLine(int[][] arr, int left, int top, int d) {
int result = 0;
for (int x = 0; x < d; x++) {
result += arr[left][top];
left++;
top++;
}
return result;
}
static int horizontalLine(int[][] arr, int left, int top, int d) {
int result = 0;
for (int x = 0; x < d; x++) {
result += arr[left][top];
top++;
}
return result;
}
static int verticalLine(int[][] arr, int left, int top, int d) {
int result = 0;
for (int x = 0; x < d; x++) {
result += arr[left][top];
left++;
}
return result;
}
}
发表于 2020-04-25 05:30:34
回复(0)
#include <iostream>
(720)#include <string>
#include <algorithm>
using namespace std;
int main() {
int N, D;
while (cin >> N >> D) {
const int n = 100;
int input[n][n];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin>>input[i][j];
}
}
int mx = 0;
// 按行
for (int i = 0; i < N; i++) {
for (int j = 0; j < N-D+1; j++) {
int temp = 0;
int t = 0;
while (t < D) {
temp += input[i][j + t];
t++;
}
mx = max(mx, temp);
}
}
// 按列
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - D + 1; j++) {
int temp = 0;
int t = 0;
while (t < D) {
temp += input[j + t][i];
t++;
}
mx = max(mx,temp);
}
}
// 左上到右下
for (int i = 0; i < N-D+1; i++) {
for (int j = 0; j < N - D + 1; j++) {
int temp = 0;
int t = 0;
while (t < D) {
temp += input[i + t][j + t];
t++;
}
mx = max(mx,temp);
}
}
// 右上到左下
for (int i = 0; i<N-D+1; i++) {
for (int j = N-1; j >D-2; j--) {
int temp = 0;
int t = 0;
while (t < D) {
temp += input[i + t][j - t];
t++;
}
mx = max(mx,temp);
}
}
// total
cout << mx << endl;
}
return 0;
}
发表于 2020-04-11 10:02:17
回复(0)
思路：扩展矩阵防止溢出
#include<iostream>
using namespace std;
main()
{
int N,D;
cin >> N >> D;
int Array[N+N+N][N+N] = {0};
int a = 0,b = 0,c = 0,d = 0;//临时存储四维加和
for(int i = N; i < (2*N); i++)
{
for(int j = 0; j < N; j++)
{
cin >> Array[i][j];
}
}
int temp = 0;//用来存储最大值
using namespace std;
main()
{
int N,D;
cin >> N >> D;
int Array[N+N+N][N+N] = {0};
int a = 0,b = 0,c = 0,d = 0;//临时存储四维加和
for(int i = N; i < (2*N); i++)
{
for(int j = 0; j < N; j++)
{
cin >> Array[i][j];
}
}
int temp = 0;//用来存储最大值
for(int i = N; i < 2*N; i++)
{
for(int j = 0; j < N; j++)
{
for(int k = 0;k < D; k++)
{
a += Array[i][j+k];
b += Array[i+k][j];
c += Array[i+k][j+k];
d += Array[i-k][j+k];
}
if(a > temp) temp = a;
if(b > temp) temp = b;
if(c > temp) temp = c;
if(d > temp) temp = d;
a = 0;
b = 0;
c = 0;
d = 0;
}
}
cout << temp << endl;
{
for(int j = 0; j < N; j++)
{
for(int k = 0;k < D; k++)
{
a += Array[i][j+k];
b += Array[i+k][j];
c += Array[i+k][j+k];
d += Array[i-k][j+k];
}
if(a > temp) temp = a;
if(b > temp) temp = b;
if(c > temp) temp = c;
if(d > temp) temp = d;
a = 0;
b = 0;
c = 0;
d = 0;
}
}
cout << temp << endl;
}
通过率百分之九十九，有人能帮我接开那个百分之一的疑惑吗
编辑于 2020-03-28 13:31:03
回复(0)
思路：对于矩阵的每一点，计算它的横，竖，右下，左下的D个数之和是否比当前最大值大，如果是则替换当前的最大值。check函数是为了判断点（x，y）是否越界
#include<iostream>
using namespace std;
bool check(int x, int y, int N);
int main()
{
//输入N和D
int N, D;
cin >> N >> D;
//输入数据
int **matrix = new int*[N];
for (int i = 0; i < N; i++) {
matrix[i] = new int[N];
}
//初始化矩阵
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> matrix[i][j];
}
}
//计算每一点开始的最大值
int max = matrix[0][0];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//计算横
if (check(j + D-1, i, N)) {
int count = 0;
for (int k = 0; k < D; k++) {
count += matrix[i][j + k];
}
max = count > max ? count : max;
}
//计算竖
if (check(i + D - 1, j, N)) {
int count = 0;
for (int k = 0; k < D; k++) {
count += matrix[i+k][j];
}
max = count > max ? count : max;
}
//左上到右下
if (check(i + D - 1, j+D-1, N)) {
int count = 0;
for (int k = 0; k < D; k++) {
count += matrix[i + k][j+k];
}
max = count > max ? count : max;
}
//右上到左下
if (check(i + D - 1, j - D + 1, N)) {
int count = 0;
for (int k = 0; k < D; k++) {
count += matrix[i + k][j - k];
}
max = count > max ? count : max;
}
}
}
cout << max;
system("pause");
return 0;
}
bool check(int x,int y,int N) {
return (x >= 0 && x < N && 0 <= y&&y < N);
}
发表于 2020-03-25 22:25:11
回复(0)
using System;
using System.Collections.Generic;
using System.Collections.Generic;
namespace Pangu_Question_2
{
internal class Program
{
private static void Main(string[] args)
{
//录入整数
var str = Console.ReadLine();
var str_1 = str.Split(' ');
var N = int.Parse(str_1[0]); //矩阵行列数
var D = int.Parse(str_1[1]); //连续整数个数
//录入矩阵
var matrix = new int[N, N];
for (var i = 0; i < N; i++)
{
var s = Console.ReadLine();
var s_1 = s.Split(' ');
for (var j = 0; j < N; j++) matrix[i, j] = int.Parse(s_1[j]);
}
{
internal class Program
{
private static void Main(string[] args)
{
//录入整数
var str = Console.ReadLine();
var str_1 = str.Split(' ');
var N = int.Parse(str_1[0]); //矩阵行列数
var D = int.Parse(str_1[1]); //连续整数个数
//录入矩阵
var matrix = new int[N, N];
for (var i = 0; i < N; i++)
{
var s = Console.ReadLine();
var s_1 = s.Split(' ');
for (var j = 0; j < N; j++) matrix[i, j] = int.Parse(s_1[j]);
}
//计算和
var sumList = new List<int>();
var sumColumn = 0; //横向和
var sumRow = 0; //纵向和
int obliqueSum; //斜线和
int obliqueIndex;
//1）计算直线和
for (var i = 0; i < N; i++)
for (var j = 0; j < N - D + 1; j++)
{
sumColumn = 0;
sumRow = 0;
for (var k = 0; k < D; k++)
{
sumColumn += matrix[i, j + k];
sumRow += matrix[j + k, i];
}
sumList.Add(sumColumn);
sumList.Add(sumRow);
}
sumList.Add(sumRow);
}
//2）计算斜线和
for (var i = 0; i < N; i++)
for (var j = 0; j < N; j++)
{
//右下方向和
obliqueSum = 0;
obliqueIndex = 0;
for (var k = 0; k < D && i + k < N && j + k < N; k++)
{
obliqueSum += matrix[i + k, j + k];
obliqueIndex++;
}
for (var i = 0; i < N; i++)
for (var j = 0; j < N; j++)
{
//右下方向和
obliqueSum = 0;
obliqueIndex = 0;
for (var k = 0; k < D && i + k < N && j + k < N; k++)
{
obliqueSum += matrix[i + k, j + k];
obliqueIndex++;
}
if (obliqueIndex == D) sumList.Add(obliqueSum);
//左上方向和
obliqueSum = 0;
obliqueIndex = 0;
for (var k = 0; k < D && i + k < N && j - k >= 0; k++)
{
obliqueSum += matrix[i + k, j - k];
obliqueIndex++;
}
//左上方向和
obliqueSum = 0;
obliqueIndex = 0;
for (var k = 0; k < D && i + k < N && j - k >= 0; k++)
{
obliqueSum += matrix[i + k, j - k];
obliqueIndex++;
}
if (obliqueIndex == D) sumList.Add(obliqueSum);
}
}
//排序输出
sumList.Sort();
Console.WriteLine(sumList[sumList.Count - 1]);
Console.Read();
}
}
}
发表于 2019-09-16 22:25:12
回复(0)
问题信息
通过挑战的用户
-
2022-09-25 20:15:47
-
2022-09-15 17:56:20 -
2022-09-03 17:56:18
-
2022-08-14 12:00:18
-
2022-08-14 11:42:48
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
