二维循环数组最大子数组的和

结对成员：于海洋袁佩佩

一.题目及要求

　　题目:返回一个二维整数数组中最大子数组的和。

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

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

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

　　　　求所有子数组的和的最大值。要求时间复杂度为O(n)。

二.设计思路

　　（1）二维数组我们采用的还是数组的形式；

（2）读取nxm的二维数组，储存成nx2m，把前m列重复加在二维数组的最后；

　　（3）搜索最大数组的方法和不循环的二维数组是一样的，就是再加上判断条件加以限制。

三.源代码

// 二维数组循环.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "fstream.h"
#include "iostream.h"
#define MAXSIZE 50
 
//*****读取数组信息*****
void ReadArr(int arr[][MAXSIZE],int &len1,int &len2)
{
    ifstream infile("Arr.txt");
    if(!infile)
        cout<<"读取失败！"<<endl;
    else
    {
        infile>>len1>>len2;
        for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                infile>>arr[i][j];            　　//从文件中读取数据
                arr[i][j+len2]=arr[i][j];
            }
        }
    }

}
//*****显示矩阵*****
void ShowArr(int arr[][MAXSIZE],int len1,int len2,int size1,int size2)
{
    for(int i=len1;i<=size1;i++)            　　　　//将文件中的数组输出
    {
        for(int j=len2;j<=size2;j++)
        {
            cout<<arr[i][j]<<"	";
        }
        cout<<endl;
    }
}
//*****求和公式*****
int GetSum(int arr[][MAXSIZE],int len1,int len2,int size1,int size2)
{
    int sum=0;
    for(int i=len1;i<=size1;i++)        　　　　　　//求任意数组中两个数之间的数的和
    {
        for(int j=len2;j<=size2;j++)
        {
            sum+=arr[i][j];
        }
    }
    return sum;
}
 
int main(int argc, char* argv[])
{
    int len1,len2,max,sum;                        //len1是行数,len2是列数
    int line1,line2,row1,row2;                    //和最大的矩阵的两个坐标
    int arr[MAXSIZE][MAXSIZE];
    ReadArr(arr,len1,len2);
    cout<<"矩阵："<<endl;
    ShowArr(arr,0,0,len1-1,len2-1);
    cout<<endl;
    line1=0;
    line2=0;
    row1=0;
    row2=0;
    sum=0;
    max=arr[0][0];
    for(int i=0;i<len1;i++)                        //第一个数的行数
    {
        for(int j=0;j<len2;j++)                    //第一个数的列数
        {
            for(int m=i;m<len1;m++)                //第二个数的行数
            {
                for(int n=j;(n<2*len2)&&(n<j+3);n++)
                {                                  //第二个数的列数
                    sum=GetSum(arr,i,j,m,n);       //求出这两个数构成的矩阵的和
                    if(sum>max)
                    {
                        max=sum;
                        line1=i;                   //保存第一个数的行
                        line2=m;                   //保存第二个数的行
                        row1=j;                    //保存第一个数的列
                        row2=n;                    //保存第二个数的列
                    }
                }
            }
        }
    }
    cout<<"和最大的子矩阵："<<endl;
    ShowArr(arr,line1,row1,line2,row2);
    cout<<"最大的和："<<max<<endl;
    return 0;
}

四.结果及截图

五.体会

　　这一次程序很快就写出来了，这是因为之前写的主要的算法比较好，所以这次我们稍微的改了一下就直接运行出来了。程序的思路比较清晰。不像第一次，那一次写的有点乱，以至于再后来拓展的时候，源程序修改不了，又重新写了一个程序。如果程序的思路结构清晰的话，对程序做一些改动的时候也会比较容易，加一些其他的功能会比较简单。

六.结对合照