结对成员：信1201-1班    黄亚萍

  信1201-1班    袁亚姣

一、题目要求

      要求：

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

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

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

            求所有子数组的和的最大值。要求时间复杂度为O(n)题目:返回一个二维整数数组中最大子数组的和。

二、设计思路

      类似于3，将二维数组转化为一维数组来求最大子数组的和，并输出其最大子数组。

三、程序源代码 

1 #include 
     
        2 #include 
      
         3 using namespace std;  4 # define M 100  5 # define N 100  6 int hang1=0;  7 int hang2=0;  8 int lie1=0;  9 int lie2=0; 10 int maxx = -100; 11 int sum1(int k,int a[],int number)    //一维数组行数元素求和 12 { 13     int x=0; 14     for(int i=k;i<=number+k-1;i++)    //数组元素的个数为number 15     { 16         x=x+a[i]; 17     } 18     return x; 19 } 20 int sum2(int k,int a[M][N],int number,int num)   //二维数组列数元素求和 21 { 22     int x=0; 23     for(int i=k;i<=number+k-1;i++)     24     { 25         x=x+a[i][num]; 26     } 27     return x; 28 } 29 int Largest1(int list1[],int length)         //一维数组求数组的子数组的和的最大值 30 { 31     int sum[N]; 32     int i,j,max=-100; 33     for(i=1;i<=length;i++)       //元素个数为i 34     {     35         for(j=1;j<=2*length-1-i+1;j++)   //子数组的第j个元素,求最大值 36         { 37              sum[j]=sum1(j,list1,i); 38              if(sum[j]>=max)  39             { 40                 max=sum[j]; 41             } 42         }         43     }     44     return max; 45 } 46  47 void Largest3(int list[],int length)          48 { 49     int sum[N]; 50     int i,j; 51     for(i=1;i<=length;i++)        52     {     53         for(j=1;j<=2*length-1-i+1;j++)   54         { 55             sum[j]=sum1(j,list,i); 56             if(sum[j]>= maxx)  57             { 58                 maxx=sum[j]; 59                 lie1 = j; 60                 lie2 = j+i-1; 61             } 62         }         63     }     64 } 65  66 int Largest2(int list[M][N],int number_x,int number_y)   //二维数组求数组的子数组的和的最大值 67 { 68     int max,m; 69     int max2[N]; 70     int sum[M][N]; 71     int max3[N]; 72     for(int i=1;i<=number_x;i++)   //数组行数为i 73     { 74         cout<<"子数组行数为"<
       <<","<
        
         =max3[i]) 90                 { 91                     max3[i]=max2[k]; 92                     hang1=m; 93                 } 94             }             95         }         96     } 97     max=max3[1]; 98     for(int n=1;n<=number_x;n++)      99     {100         if(max3[n]>=max)101         {102             max=max3[n];103             hang1=m;104             hang2=n;      //子数组的行数为第m行到第m+n行105 106         }107     }            108     return max;109 }110 void show(int arry[N][N],int length1,int length2)   //输出矩阵111 {112     for(int i=1;i<=length1;i++)113     {114         for(int j=1;j<=length2;j++)115         {116             cout<
         
          <<"\t";117         }118         cout<
          
           >number_hang>>number_lie;132 for(int i=1;i<=number_hang;i++)133 {134 for(int j=1;j<=number_lie;j++)135 {136 infile>>list[i][j];137 }138 }139 }140 141 cout<<"以矩阵形式展示为："<
          
         
        
      
     

四、运行结果截图

五、心得体会

在这个过程中，我在深深的我们的默契越来越好了，我们在一起讨论问题，整个问题也越来越复杂，但是在原来的基础上，感觉难度小了许多。