首页 > 代码库 > 返回一个整数最大连通数组和
返回一个整数最大连通数组和
一、实验题目
二维数组的最大联通子图和
二、实验思想
1、先在主函数内输入行数和列数,然后利用for循环进行对二维数组的赋值。
2、调用求最大值的函数求二维数组的联通最大值。
3、其中当列数为1时,需要另外考虑,当成一维的计算,其它的情况利用先求每行的最大和最小块,然后进行最后的求总的最大值,然后返回进行输出最大值。
三、实验代码
import java.util.Scanner;
import javax.print.attribute.standard.PrinterLocation;
public class Maxshuzu
{
public static void main(String[] args)
{
Scanner scanner=new Scanner(System.in);
System.out.println("请输入二维数组的行和列:");
int hang=scanner.nextInt();
int lie=scanner.nextInt();
int[][] shuzu=new int[hang][lie];
int i,j;
for(i=0;i<hang;i++)
{
for(j=0;j<lie;j++)
{
shuzu[i][j]=scanner.nextInt();
}
}
System.out.println("此数组中连续和的最大值为:"+max(shuzu,hang,lie));
}
static int max(int shuzu[][],int hang,int lie)
{
int max=0,sum=0;
int i,j;
int[] b=new int[lie];
int[] up=new int[hang];
int[] down=new int[hang];
int[] t=new int[hang];
if(lie==1)
{
for (i=0;i<hang;i++)
{
sum+=shuzu[i][0];
if(sum<0)
{
sum=0;
}
if(sum>max)
{
max=sum;
}
}
if(max==0)
{
for(i=0;i<hang;i++)
{
if(i==0)
{
max=shuzu[i][0];
}
if(shuzu[i][0]>max)
{
max=shuzu[i][0];
}
}
}
}
else
{
for(i=0;i<hang;i++)
{
for(j=0;j<lie;j++)
{
b[j]=shuzu[i][j];
}
int[] c=new int[100];
c[0]=0;
int sum1=0,max1=0,k;
for(k=0;k<lie;k++)
{
if(sum1<0)
{
sum1=b[k];
}
else
{
sum1=sum1+b[k];
}
c[k]=sum1;
}
max1=c[0];
int mmark=0,smark=0;
for(k=0;k<lie;k++)
{
if (max1<c[k])
{
max1= c[k];
mmark = k;
}
}
for (k = mmark;k >= 0;k--)
{
if (c[k] == b[k])
{
smark = k;
break;
}
}
sum=max1;
up[i]=smark;
down[i]=mmark;
t[i]=sum;
}
int t2=t[0];
for(i=0;i<hang-1;i++)
{
if(up[i]<=down[i+1] && down[i]>=up[i+1])
{
t2+=t[i+1];
}
for(j=up[i];j<up[i+1];j++)
{
if(shuzu[i+1][j]>0) t2+=shuzu[i+1][j]; //判别独立正数
}
返回一个整数最大连通数组和