求二维数组环的最大的子数组的和
#include<iostream> using namespace std; void max(int row,int col) { int ** a=new int*[row+1]; int ** b=new int*[row+1]; int h;//用于每一个一维数组上已经相加元素的个数够一个环则开始下一个 for(int i=1;i<=row;i++) { a[i]=new int[2*col]; } for(int i=1;i<=row;i++) { b[i]=new int[2*col]; } cout<<"请输入"<<row<<"行"<<col<<"列的数组的元素"<<endl; int count=0; for(int i=1;i<=row;i++) { for(int j=1;j<=col;j++) { cin>>a[i][j]; b[i][j]=a[i][j]; if(a[i][j]<0) { count++; } } } for(int i=1;i<=row;i++)//将二维数组加倍成环 { for(int j=col+1;j<=2*col-1;j++) { a[i][j]=a[i][j-col]; } } /*cout<<"所输入的数组为:"<<endl; for(int i=1;i<=row;i++) { for(int j=1;j<=2*col-1;j++) { cout<<a[i][j]<<" "; } cout<<endl; }*/ int k,n=2; if(count<row*col)//即不是所有的元素都是负数的情况 { int sum=0; for(int m=1;m<=row;m++) { k=n; for(int i=1;i<=row;i++) { for(int j=1;j<=2*col-1;j++) { b[i][j]=a[i][j]; } }//b[i]是经过元算后的数组而a[i]用于保留原数组 for(int i=m;i<=row;i++) { while(k<=i)//只有在行数大于等于2时才出现两行相加 { for(int j=1;j<=2*col-1;j++) { b[k][j]=b[k-1][j]+b[k][j]; } k++; } } /*cout<<"b"<<endl; for(int i=1;i<=row;i++) { for(int j=1;j<=2*col-1;j++) { cout<<b[i][j]<<" "; } cout<<endl; }*/ n++; for(int i=m;i<=row;i++) { int c=0; h=1; while(h<=col) { for(int j=h;j<=col-1+h;j++) { if(c<0) { c=b[i][j]; } else { c=c+b[i][j]; } if(sum<c) { sum=c; } //cout<<sum<<" "; } h++; c=0;//一圈结束c清零sum保持 } } } cout<<endl; cout<<"最大子数组的和为:"<<sum; } else { int sum=a[1][1]; for(int i=1;i<=row;i++) { for(int j=1;j<=col;j++) { if(a[i][j]>sum) { sum=a[i][j]; } } } cout<<endl; cout<<"最大子数组的和为:"<<sum; } for(int i=1;i<=row+1;i++)//删除动态数组 { delete []a[i]; a[i]=NULL; } for(int i=1;i<=row+1;i++)//删除动态数组 { delete []b[i]; b[i]=NULL; } } void main() { int row,col;//行和列数 cout<<"请输入数组的行数和列数:"; cin>>row>>col; max(row,col); }
结果截图:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。