结对开发2__最大子数组

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

一、问题要求　　　　

　　　程序要使用的数组放在一个叫 input.txt 的文件中, 文件格式是:

　　　　　数组的行数,

　　　　　数组的列数,

　　　　　每一行的元素, (用逗号分开)

　　　　　每一个数字都是有符号32位整数, 当然, 行数和列数都是正整数。

　　　例如下面的文件说明数组是有1行, 6列, 元素依次是: 5, 6, –3, 8, –9, 2

二、算法思想

　　1、对于文件的处理

　　　　运用C++中文件流的方式读出文件中的内容。

　　2、对于求子数组值的问题

　　　　根据问题的要求，我们的解决思想是：定义两个点p1(x1,y1),p2(x2,y2)分别代表初始点和末尾点，

　　这样，两个点就可以代表子数组的左上方的顶点和右下方的顶点，然后用循环将子数组的元素依次相加，最后

　　储存在一个数组里。

三、源代码

/*======================================================================
            # Author: TianYongTao&&ZhangYaPeng
            # E-Mail: [email protected]
            # Last modified: 2015-03-25 22:13
            # Filename: Demo.cpp
            # Description: 
======================================================================*/
# include <iostream>
# include <stdio.h>
# include <fstream>
# include <string>
# define MaxRow 20
# define MaxCol 20
using namespace std;
int Arr[MaxRow][MaxCol];

int SumArr(int x1,int y1,int x2,int y2)                    //子数组求和
{
    int sum=0;
    for(int i=x1;i<x2;i++)
    {
        for(int j=y1;j<y2;j++)
        {
            sum+=Arr[i][j];
        }
    }
    return sum;
}

void LoadFile(int Arr[][MaxCol],int & Row,int & Col)            //读取文件到数组
{
    FILE * infile = fopen("D:\\input.txt","r");
    int num[100];
    int count=0;
    if(!infile)
    {
        cout<<"文件读取失败!"<<endl;
        exit(-1);
    }
    else
    {
        char str[10];
        fscanf(infile,"%[^,]%*c",str);                        //使用正则表达式过滤掉‘,‘
        Row = atof(str);
        fscanf(infile,"%[^,]%*c",str);
        Col = atof(str);
        while(!feof(infile))                                    //此时读取的是数组的内容  先将其放入一个整型数组
        {
            fscanf(infile,"%[^,]%*c",str);
            num[count++]=atof(str);
        }
    }
    for(int i=Row-1;i>=0;i--)                                //将整型数组内容放入Arr数组中
    {
        for(int j=Col-1;j>=0;j--)
        {
            Arr[i][j]=num[--count];
        }
    }
}

//测试函数
int main()
{
    int Row=0;
    int Col=0;
    LoadFile(Arr,Row,Col);
    int x1,y1;                                            //代表左上角点的横纵坐标
    int x2,y2;                                            //代表右上角点的横纵坐标
    int max = Arr[0][0];                            //max存储比较过程中的最大值
    for(x1=0;x1<Row;x1++)
    {
        for(y1=0;y1<Col;y1++)
        {
            for(x2=x1+1;x2<=Row;x2++)
            {
                for(y2=y1+1;y2<=Col;y2++)
                {
                    if(SumArr(x1,y1,x2,y2)>max)
                    {
                        max = SumArr(x1,y1,x2,y2);
                    }
                }
            }
        }
    }
    cout<<"该数组的最大子数组的和为:"<<max<<endl;
    return 0;
}