返回一个二维整数数组中最大联通子数组的和

要求：

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

求所有子数组的和的最大值。下面是给的示例图：

 

 

设计思路：

     数组的行和列和数组元素又文件读入，然后把数按行分成几个一维数组，对于该一维数组，求出他们的最大连续数组之和，并且记录下最大连续数组的第一位和最后一位的位置，之后判断几个一维数组的最大连续数组的位置是否相接或包括。最后在加上没有包括的正数（必须在上一行的最大连续数组的第一位和最后一位的位置之间），输出之前加和。

 

程序源代码：

//2016/4/1 求最大联通子数组的和——赵子茵&孔宇航#include
     
      #include
      
       using namespace std;int Max(int n, int arr[], int *Start_mark, int *Final_mark){    int step[100] = { 0 };//Step记录每步计算子数组的和    int i, sum = 0, max1 = 0;    /* sum是子数组的和       max1是子数组最大和    */    for (i = 0; i
       
        = 0; i--)    {        if (step[i] == arr[i])        {            *Start_mark = i;            break;        }    }    return max1;}void main(){    int m, n, i, j, Start_mark, Final_mark, big;    int Max1;    int read[10000];//读取文件的字符集    int up[100], down[100], h[100];    int Arr2[100][100], Arr1[100];    /* m行n列的数组       Start_mark表示最大子数组的起始坐标       Final_mark表示最大子数组的终止坐标       big表示最后输出的最大联通子数组和       Max1是函数返回的一维数组最大子数组和       up存放每行最大子数组起始坐标       down存放每行最大子数组终止坐标       h存放每行最大子数组的和       Arr2存放二维数组       Arr1存放拆成的一维数组    */    //文件输入    ifstream infile("input.txt", ios::in);    if (infile.is_open() == false)    {        cerr << "open error!" << endl;        exit(1);    }    infile >> read[0];//读取行数m    m = read[0];    infile >> read[1];//读取列数n    n = read[1];    cout << "指定文件中" << read[0] << "行 " << read[1] << "列的二维数组如下：" << endl;    for (i = 0; i < m; i++)//读取数组并按格式输出    {        for (j = 0; j < n; j++)        {            infile >> read[i + 2];            Arr2[i][j] = read[i + 2];            cout << Arr2[i][j] << " ";            if (j % (n - 1) == 0 && j != 0)                cout << endl;        }    }    infile.close();    //把二维数组按行分解为几个一维数组    for (i = 0; i
        
         = up[i + 1])//联通，则相加            big += h[i + 1];        for (j = up[i]; j
         
          0)//是否独立正数，有则加                big += Arr2[i + 1][j];             }    }    cout << "此二维数组的最大联通子数组的和为：" << endl;    cout << big << endl;    }
         
        
       
      
     

 

运行结果截图：

 

实验总结：

  对于本次实验，我们最开始尝试过遍历数组的方法，设置了结构体，将数组的数设置坐标，但是后来没有掌握好方法以失败告终。在课堂上受到同学的启发将二维数组编程一位数组，比如第一行和第二行加和后出现新的一位数组的方法，在网上阅读了写别人的思路，最后和小伙伴写出了这个程序。这个程序存在缺陷，个别的测试用例会出错，现在的程序只能解决最大连续数组相连的，还不能解决不相连的，对于最后今加上剩余的正数，只会加上与第一行重合的，第三行以及以下的行并不加上前一步加上的第二行的正数。这个缺陷会在以后慢慢完善，希望老师谅解。

   合作小伙伴:赵子茵童鞋

   链接：