二位数组升级版

浏览数：19 / 时间：2015年06月08日

一、题目及要求：

返回一个整数数组中最大子数组的和

输入一个二维整形数组，数组里有正数也有负数；二维数组首尾相接，像一条首尾相接的带子一样。

二、设计思路：

这个题目其实与上次毫无区别，仍然调用循环一维数组求最大子数组的函数，将二维数组列的情况全

部列出，即转化为一维数组。a[0][0]，a[0][0]a[0][1]........。在调用函数即可。

三、源代码

#include<iostream.h>
int max2(int arry[],int length)  //跨越arry[n-1]、arry[0]的最大和
{
    int total=0;
    int sum=arry[0];
    int minsum=arry[0];
    for(int i=1;i<length;i++)
    {
        if(sum>0)
        {
            sum=arry[i];
        }
        else
        {
            sum=sum+arry[i];

        }
        if(minsum>=sum)
        {
            minsum=sum;
        }
        total=total+arry[i];
    }
    total=total+arry[0];
    minsum=total-minsum;

    return minsum;
}


int max1(int arry[],int length)   //不跨越零点的最大和
{
    int sum=arry[0];
    int maxsum=arry[0];
    for(int i=1;i<length;i++)    //求出相邻数组最小和
    {
        if(sum<0)
        {
            sum=arry[i];
        }
        else
        {
            sum=sum+arry[i];

        }
        if(maxsum<=sum)
        {
            maxsum=sum;
        }
    }
    //struct ret ret1={maxsum,start2,end};
    return maxsum;
}
int column(int a[][20],int length,int num1) //求最大和
  {
      int y=0;
      int d[20];
      int e[100];
      int c[100][20];
      c[0][0]=0;
      int p=0;
      int b[100]={0};
      for(int j=0;j<num1;j++)
      {
          for(int t=j;t<num1;t++)
          {
              for(int i=0;i<length;i++)
              {
                  b[i]=b[i]+a[t][i];
                  c[p][i]=b[i];
              }
              p=p+1;
          }
          for(int o=0;o<100;o++)
          {
              b[o]=0;
          }
      }
      for(int l=0;l<p;l++)
      {

          for(int u=0;u<length;u++)
          {
              d[u]=c[l][u];
              //cout<<d[u]<<"  ";
          }
          e[y++]=max1(d,length);
          e[y++]=max2(d,length);
          //cout<<e[y-1]<<"  ";
      }
      int Max=e[0];
      for(int i=0;i<y;i++)
      {

          if(e[i]>=Max)
         {
             Max=e[i];
            }
         }
      return Max;
}
 int main()
{
     int a[20][20];
     int length,index;

     cout<<"输入行数列数:";
     cin>>index>>length;

     int y=0;
     for(int i=0;i<index;i++)
     {
         for(int j=0;j<length;j++)
         {
             cin>>a[i][j];
         }
     }

     int s=column(a,length,index);
     cout<<"最大和为:"<<s<<endl;
     return 0;
 }