1、题目:

返回一个二维数组中最大子数组的和。

2、要求：

输入一个二维整形数组，数组里有正数也有负数。

二维数组首尾相接，象个一条首尾相接带子一样。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

3、结对开发要求:

两人结对完成编程任务。

一人主要负责程序分析，代码编程。

一人负责代码复审和代码测试计划。

发表一篇博客文章讲述两人合作中的过程、体会以及如何解决冲突。

二、设计思路

1、输入一个既有正数又有负数的数组，并把它变为环形二维数组。

2、声明一个Sum()函数，用来计算子数组的和。

3、用两个坐标，左上角为(x1,y1)，右下角为(x2,y2)，这样就可以实现在遍历数组的时候确定子数组，并调用Sum()函数计算出最大值，并用坐标标记位置输出。

三、代码

#include<iostream.h>

int Array[100][100];

int Sum(int x1,int y1,int x2,int y2) //计算子数组和的函数

{

int sum=0;

for(int i=x1;i<x2;i++)

{

for(int j=y1;j<y2;j++)

{

sum+=Array[i][j];

}

}

return sum;

}

int main()

{

int row;

int col;

int i,j,x1,x2,y1,y2;

/**********************************/

cout<<"输入整数数组的行数:";

cin>>row;

cout<<endl;

cout<<"输入整数数组的列数:";

cin>>col;

cout<<endl;

/************************************/

int Arr[100][100]; //存放键盘输入的数组

/*******输入数组内元素**************/

cout<<"输入整数数组元素:"<<endl;

for(i=0;i<row;i++)

{

for(j=0;j<col;j++)

{

cin>>Arr[i][j];

}

}

/*******输出数组内元素*************/

cout<<"整数数组如下:"<<endl;

for(i=0;i<row;i++)

{

for(j=0;j<col;j++)

{

cout<<Arr[i][j]<<" ";

}

cout<<endl;

}

/*******生成二维环形数组***********/

for(i=0;i<row;i++)

{

for(j=0;j<col;j++)

{

Array[i][j] = Arr[i][j];

Array[i][j+col] = Arr[i][j];

}

}

/*for(i=0;i<row;i++) //输出环形数组

{

for(j=0;j<2*col-1;j++)

{

cout<<Array[i][j]<<" ";

}

cout<<endl;

}*/

/************************************/

int flag1,flag2,flag3,flag4;

flag1=flag2=flag3=flag4=0;

int max=Array[0][0];

for(x1=0;x1<row;x1++) //遍历数组求最大子数组的和

{

for(y1=0;y1<col;y1++)

{

for(x2=x1+1;x2<=row;x2++)

{

for(y2=y1+1;y2<=2*col;y2++)

{

if((y2-y1) > col)

{

break;

}

if(Sum(x1,y1,x2,y2)>max)

{

max = Sum(x1,y1,x2,y2); //用两个坐标(flag1,flag2),(flag3,flag4)表示最大子数组

flag1=x1;

flag2=y1;

flag3=x2;

flag4=y2;

}

}

}

}

}

cout<<"最大子数组为:"<<endl;

for(i=flag1;i<flag3;i++) //使用坐标显示子数组

{

for(j=flag2;j<flag4;j++)

{

cout<<Array[i][j]<<"\t";

}

cout<<endl;

}

cout<<"该最大子数组的和为:"<<max<<endl;

return 0;

}

四、运行结果

五、结对认照片