课堂练习:返回一个二维数组中最大子数组的和
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了课堂练习:返回一个二维数组中最大子数组的和,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2151字,纯文字阅读大概需要4分钟。
内容图文
![课堂练习:返回一个二维数组中最大子数组的和](/upload/InfoBanner/zyjiaocheng/1182/8d881135c9084f0f95471fc00a676480.jpg)
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;
}
四、运行结果
五、结对认照片
原文:https://www.cnblogs.com/f135114/p/9904411.html
内容总结
以上是互联网集市为您收集整理的课堂练习:返回一个二维数组中最大子数组的和全部内容,希望文章能够帮你解决课堂练习:返回一个二维数组中最大子数组的和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。