AcWing 126. 最大的和
原题链接
简单
作者:
季之秋
,
2021-02-22 22:57:35
,
所有人可见
,
阅读 297
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int s[][]=new int[110][110];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int a=sc.nextInt();
s[i][j]=s[i-1][j]+a;//前缀和方便计算每一个点(边界内的每一列值的和)的值
}
int res=-30000;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){ //遍历行的所有上边界和下边界,边界内看成求最大区间合
int f=0; //最大区间和
for(int k=1;k<=n;k++){ //遍历列 以k结尾区间的最大和
int w=s[j][k]-s[i-1][k]; //单个点上的值就是上边界到下边界的权值和
f=Math.max(f,0)+w;
//集合划分:只有单个元素“k"或以k-1结尾的最大区间和f[k-1] + k的值
res=Math.max(res,f);
//所有二维区间和f的最大值
}
}
}
System.out.println(res);
}
}