求数组中最大子数组的和（二维环）
成员：林彦汝、张金
(这次角色调换，我主要负责代码复审，代码测试计划；张金负责程序分析，代码编程。)
题目:
返回一个二维整数数组中最大子数组的和
要求：
输入一个二维整形数组，数组里有正数也有负数。
二维数组首尾相接，象个一条首尾相接带子一样。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。
思路：
在求一维环形数组和二维数组最大子数组的和的基础上，我们将两个的方法综合起来求解关于二维环形数组。假设原二维数组a[3][3]为
|
1 |
-2 |
3 |
|
1 |
-3 |
2 |
|
3 |
-4 |
5 |
在创建一个新的二维数组b[3][5]为
|
1 |
-2 |
3 |
1 |
-2 |
|
1 |
-3 |
2 |
1 |
-3 |
|
3 |
-4 |
5 |
3 |
-4 |
把它分割为三个子数组，分别为：
|
1 |
-2 |
3 |
|
1 |
-3 |
2 |
|
3 |
-4 |
5 |
|
-2 |
3 |
1 |
|
-3 |
2 |
1 |
|
-4 |
5 |
3 |
|
3 |
1 |
-2 |
|
2 |
1 |
-3 |
|
5 |
3 |
-4 |
每个子数组都像之前二维数组那样的方法，求出每个子数组的最大子数组，最后再比较。
源代码：
#include<iostream.h>
#include<conio.h>
int main()
{
int i,j;
int a[3][3];
int b[3][5];
int jixu;
cout<<"本程序解决3*3矩阵的首尾相连求最大子矩阵和的问题"<<endl;
cout<<"请输入3*3矩阵的各个数值"<<endl;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cin>>a[i][j];
}
}
int max=a[0][0];
cout<<"初始二维数组为："<<endl;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
cout<<a[i][j]<<‘ ‘;
}
cout<<endl;
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
b[i][j]=a[i][j];
b[i][j+3]=a[i][j];
}
}
cout<<"首尾相连后的数组为："<<endl;
for(i=0;i<3;i++)
{
for(j=0;j<5;j++)
{
cout<<b[i][j]<<‘ ‘;
}
cout<<endl;
}
for(i=0;i<1;i++)
{
b[0][0]=a[0][0];
for(j=0;j<5;j++)
{
if(a[0][j-1]<0)
{
b[0][j]=a[0][j];
}
else
{
b[0][j]=b[0][j-1]+a[0][j];
}
}
}
for(i=1;i<3;i++)
{
for(j=0;j<1;j++)
{
if(a[i-1][0]<0)
{
b[i][0]=a[i][0];
}
else
{
b[i][0]=b[i-1][0]+a[i][0];
}
}
}
for(i=1;i<3;i++)
{
for(j=1;j<5;j++)
{
if(b[i-1][j-1]<0)
{
if(b[i-1][j]>=0&&b[i][j-1]>=0)
{
if(b[i][j-1]>=b[i-1][j])
{
b[i][j]=b[i][j-1]+a[i][j];
}
else
{
b[i][j]=b[i-1][j]+a[i][j];
}
}
else if(b[i-1][j]>=0&&b[i][j-1]<=0)
{
b[i][j]=b[i-1][j]+a[i][j];
}
else if(b[i-1][j]<=0&&b[i][j-1]>=0)
{
b[i][j]=b[i][j-1]+a[i][j];
}
else
{
b[i][j]=a[i][j];
}
}
else
{
if(b[i-1][j]>=0&&b[i][j-1]>=0)
{
b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
else if(b[i-1][j]>=0&&b[i][j-1]<=0)
{
b[i][j]=a[i][j]+b[i-1][j]-b[i-1][j-1];
}
else if(b[i-1][j]<=0&&b[i][j-1]>=0)
{
b[i][j]=a[i][j]+b[i][j-1]-b[i-1][j-1];
}
else
{
b[i][j]=a[i][j];
}
}
}
}
cout<<"求最大子矩阵和的中间过程："<<endl;
for(i=0;i<3;i++)
{
for(j=0;j<5;j++)
{
cout<<b[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
for(i=0;i<3;i++)
{
for(j=0;j<5;j++)
{
if(b[i][j]>max)
{
max=b[i][j];
}
}
}
cout<<"所求二维数组的最大字数组和为："<<max+1<<endl;
cout<<"是否要继续此过程（jixu）1,继续 0，退出"<<endl;
cin>>jixu;
if(jixu==1)
{
cout<<endl;
main();
}
else
{
return 0;
}
getch();
return 0;
}
运行结果：
总结：
这次我和小伙伴互换了角色，我主要负责代码审查。首先我们确定了思路和解决方法的方向，由于时间的安排，代码的主体一起讨论编写完，而循环找出最大子数组等一些细节是一个人写的。在后来审查代码的时候，发现有些地方跟之前讨论的和前一次二维数组的方法有些不一样，可能是因为我们的思维方式和掌握求解问题的方法不同。
在测试多组数据后发现了一些问题和缺陷，告诉了搭档，进行修改完善。关于3*3这个固定的二维数组，这个局限性很大，还没有修改。
经过这几次的课堂练习，我发现弱点在于确定思路。虽然在看到问题后会突然冒出很多想法，但提出之后就想出更多的特殊情况来一一否定自己，再听在讲台上发言的同学分享他们自己的思路后（其实有些跟自己的差不多一样），又觉得确实可行。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
