首页 > 代码库 > 二维数组最大子数组（结对开发）
二维数组最大子数组（结对开发）
1.题目要求
题目:返回一个二维整数数组中最大联通子数组的和。 要求： 输入一个二维整形数组，数组里有正数也有负数。 求所有子数组的和的最大值。
2.设计思想:
对n*m的二维数组进行分解，分解为n个一维数组，再先求这n个一维数组的最大子数组和，并记下每行最大一维子数组的下标如2-5，这是就会分两种情况第一种是行之间的最大子数组是相连的，如第一行是2-5，第二行是3-6，这是直接相加就行。第二种是不相连的如第一行是2-5，第二行是6-7，这时候就把每行的最大子数组看成一个整体，再使每个最大数组块进行相连，求使其相连的最小代价。最后就可求出最大联通子数组的和。
3.代码:
package erweishuzu;
import java.util.Scanner;
public class shuzu {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[][]=new int[20][20];
Scanner str=new Scanner(System.in);
System.out.print("请输入二维数组的行数列数:");
int index=str.nextInt();
int length=str.nextInt();
int y=0;
System.out.println("请输入数组:");
for(int i=0;i<index;i++)
{
for(int j=0;j<length;j++)
{
a[i][j]=str.nextInt();
}
}
int s=sum(a,length,index);
System.out.println("最大连通子数组和:"+s);
}
public static int max2(int arry[],int length)
{
int total=0;
int sum=arry[0];
int minsum=arry[0];
for(int i=1;i<length;i++)
{
if(sum>0)
{
sum=arry[i];
}
else
{
sum=sum+arry[i];
}
if(minsum>=sum)
{
minsum=sum;
}
total=total+arry[i];
}
total=total+arry[0];
minsum=total-minsum;
return minsum;
}
public static int max1(int arry[],int length)
{
int sum=arry[0];
int maxsum=arry[0];
for(int i=1;i<length;i++)
{
if(sum<0)
{
sum=arry[i];
}
else
{
sum=sum+arry[i];
}
if(maxsum<=sum)
{
maxsum=sum;
}
}
return maxsum;
}
public static int sum(int a[][],int length,int num1)
{
int y=0;
int d[]=new int[20];
int e[]=new int[100];
int c[][]=new int[100][20];
c[0][0]=0;
int p=0;
int[] b=new int[100];
b[0]=0;
for(int j=0;j<num1;j++)
{
for(int t=j;t<num1;t++)
{
for(int i=0;i<length;i++)
{
b[i]=b[i]+a[t][i];
c[p][i]=b[i];
}
p=p+1;
}
for(int o=0;o<100;o++)
{
b[o]=0;
}
}
for(int l=0;l<p;l++)
{
for(int u=0;u<length;u++)
{
d[u]=c[l][u];
}
e[y++]=max1(d,length);
e[y++]=max2(d,length);
}
int Max=e[0];
for(int i=0;i<y;i++)
{
if(e[i]>=Max)
{
Max=e[i];
}
}
return Max;
}
}
3.运行结果截图:
4.总结分析:
伙伴康杨主要负责程序分析，代码编程，本人主要负责代码复审和代码测试计划。
在实验的开始，我们对数组的思考，将其转换为图的方法来解决问题，对之前学过的知识来说是一个很好的利用，实验过程中开始我们对结构的使用比较陌生，之前编程用到的少，再查阅相应资料后得以实现，总之通过这次结对开发的实验设计，收获很多，学到了很多。 编程过程中主找最大联通子数组还是比较难的一个问题。
康杨博客地址：http://www.cnblogs.com/kangy123/p/6679552.html
二维数组最大子数组（结对开发）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。