查找二维数组list[][]中的最大的子数组的和

之前做过最大一维数组子数组的和的题目,现在将数组扩展成二维:

代码如下:

#include<iostream>
#define null -858993460
using namespace std; void main()
{
int arr[]={,,,-,,-,};
int arr2[]={-,-,-,-};
int arr3[]={};
int arr4[]={,,};
int arr5[];
int a[][]={{,,-,,-,},{,-,,,-,-},{-,-,-,,,-}};
int b[][];
int c[][]={{-,-,-},{-,-,-},{-,-,-}}; int yiwei_maxsub_list(int list[],int length);
int erwei_maxsub_list(int list[][],int x,int y); cout<<"一维数组:"<<endl;
cout<<yiwei_maxsub_list(arr,)<<endl;
cout<<yiwei_maxsub_list(arr2,)<<endl;
cout<<yiwei_maxsub_list(arr3,)<<endl;
cout<<yiwei_maxsub_list(arr4,)<<endl;
cout<<yiwei_maxsub_list(arr5,)<<endl; cout<<"二维数组:"<<endl;
cout<<erwei_maxsub_list(a,,)<<endl;
cout<<erwei_maxsub_list(b,,)<<endl;
cout<<erwei_maxsub_list(c,,)<<endl; } int yiwei_maxsub_list(int list[],int length)
{
int a[]={};
int max;
int i,j;
int k=; if(list==NULL||length==)
{
cout<<"error!inter is null!";
return ;
} for(i=;i<length;i++)
{
a[k]=list[i];
for(j=i;j<length;j++)
{
a[k+]=a[k]+list[j+];
k++;
}
}
max=a[];
for(i=;i<k;i++)
{
if(max<a[i])
{
max=a[i];
} }
return max;
} int erwei_maxsub_list(int list[][],int x,int y)
{//int list[][100]={{5,6,-3,8,-9,2},{1,-12,20,0,-3,-5},{-9,-7,-3,6,7,-1}};x=3,y=6
int a[][]={};
int b[][]={};
int max,i,j,n;
int t,k;//t行扩展后的,k列扩展
if(list==NULL||x==||y==)//异常处理
{
cout<<"error!inter is null!";
return ;
} for(n=;n<x;n++)//n层(x)
{
k=;
for(i=;i<y;i++)
{
a[n][k]=list[n][i];
for(j=i;j<y;j++)
{
a[n][k+]=a[n][k]+list[n][j+];
k++;
}
}
}
t=k;
for(n=;n<t;n++)//n列(t)
{
k=;
for(i=;i<x;i++)
{
b[k][n]=a[i][n];
for(j=i;j<x;j++)
{
b[k+][n]=b[k][n]+a[j+][n];
k++; }
}
} max=list[][]; for(i=;i<k;i++)
{
for(j=;j<t;j++)
if(max<b[i][j])
{
max=b[i][j];
}
}
return max; }

截图:

查找二维数组list[][]中的最大的子数组的和

时间:用时,在一维数组的前提下1小时;

方法:将二维数组参数传入函数后,函数将数组先进行行扩展,每行记录单独一行的子数组,然后列扩展,将原来的二维数组扩展为子数组和的数组,然后遍历扩展后的数组找到最大值;这样时间复杂度是(m+n)².

总结:这其实体现了敏捷开发中的问题,用户的需求不断改变,团队的效率建立在过去的基础上,迭代开发的效率会比较高。这也是现在软件开发的主流,需要团队合作,代码规范,程序结构完整,健壮性强等等。再今后的软件工程学习和运用中深入体会。

上一篇:堆结构的优秀实现类----PriorityQueue优先队列


下一篇:apache 配置反向代理 设置