最大联通子数组

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

要求： 1. 输入一个二维整形数组，数组里有正数也有负数。求所有子数组的和的最大值。要求时间复杂度为O(n)。

2.程序要使用的数组放在一个叫 input.txt 的文件中，文件格式是: 数组的行数, 数组的列数, 每一行的元素， (用逗号分开) 每一个数字都是有符号32位整数，当然，行数和列数都是正整数。

分析：矩阵中的数是随机生成的，可能会有正有负，所以要首先判断二维数组中哪些位置上的数是正数，利用另一个二维数组记录正数的位置，然后判断哪些数是连通的，我的思路是先判断两个数的行数（列数）是否相同，如果相同，再判断列数（行数）是否相邻，如果相邻即证明两个数连通，计算每个连通块的数值的和，然后再连通不同的块，计算其和，最后比较其中的最大值，即为二维整数数组中最大联通子数组的和。

代码：

  1 #include<iostream>
  2 #define N 100
  3 #include<ctime>
  4 #include <fstream>
  5 using namespace std;
  6 
  7 typedef struct
  8 {
  9     int d[N];
 10     int a[N][N];
 11     int x;
 12 }A;
 13 void set(A &array, int x, int y)//x,y分别是行数和列数
 14 {
 15     array.x = x*y;
 16     srand((unsigned)time(NULL));
 17     for (int i = 1; i <= array.x; i++)
 18     {
 19         array.d[i] = rand() % 10;
 20         if (rand() % 2 == 1)
 21             array.d[i] = array.d[i] * (-1);
 22     }//随机生成数组的数
 23     for (int i = 1; i <= array.x; i += y)
 24     {
 25         for (int j = i; j <= i + y - 2; j++)
 26         {
 27             array.a[j][j + 1] = 1;
 28             array.a[j + 1][j] = 1;
 29         }
 30     } for (int i = 1 + y; i<array.x; i += y)
 31     {
 32         for (int j = i; j <= i + x - 1; j++)
 33         {
 34             array.a[j][j - y] = 1;
 35             array.a[j - y][j] = 1;
 36         }
 37     }//将随机生成的一维数组转换成二维的图的形式
 38 }
 39 void output(A array)
 40 {
 41     for (int i = 1; i <= array.x; i++)
 42     {
 43         cout << array.d[i];
 44         if (array.a[i][i + 1] == 1)
 45             cout << "  ";
 46         else 
 47             cout << endl;
 48     }
 49 }
 50 void bianli(A &array, int v, int visit[], int&b, int&max, int x)
 51 {
 52     visit[v] = 1;
 53     max += array.d[v];
 54     if (max >= b)
 55         b = max;
 56     int a = 0, bo = 0;
 57     for (int w = 1; w <= array.x; w++)
 58     {
 59         for (int c = 1; c <= array.x; c++)
 60         {
 61             if ((visit[w] == 0) && (array.a[c][w] == 1) && (visit[c] == 1))
 62             {
 63                 a = w;
 64                 bo = 1;
 65                 break;
 66             }
 67         }
 68         if (bo == 1) break;
 69     }
 70     for (int w = 1; w <= array.x; w++)
 71     {
 72         for (int c = 1; c <= array.x; c++)
 73         {
 74             if ((visit[w] == 0) && (array.a[c][w] == 1) && (visit[c] == 1))
 75             {
 76                 if (array.d[a]<array.d[w])
 77                     a = w;
 78             }
 79         }
 80     }
 81     if (b + array.d[a]<0)
 82     {
 83         array.a[v][a] = 0;
 84     }
 85     else
 86         bianli(array, a, visit, b, max, x);
 87 }
 88 //遍历
 89 int NoVisit(int visit[], A array)
 90 {
 91     int k = 0, i;
 92     for (i = 1; i <= array.x; i++)
 93     {
 94         if (visit[i] == 0)
 95         {
 96             k = i;
 97             break;
 98         }
 99     } return k;
100 }//判断图中没有visit的项
101 int main()
102 {
103     int x, y;
104     ofstream outfile;
105     outfile.open("intput.txt");
106     if (!outfile)
107     {
108         cerr << "OPEN ERROR!" << endl;
109         exit(0);
110     }
111     cout << "输入数组的行:" << endl;
112     cin >> x;
113     outfile << x << endl;
114     cout << "输入数组的列：" << endl;
115     cin >> y;
116     outfile << y << endl<<endl;
117     A array;
118     set(array, x, y);
119     output(array);
120     int v = 1, b[N] = { 0 }, h = 0;
121     for (int i = 1; i <= array.x; i++)
122     {
123         if (array.d[i]<0)
124         {
125             b[i] = array.d[i];
126         }
127         else
128         {
129             int visit[N] = { 0 };
130             int max = 0;
131             bianli(array, i, visit, b[i], max, x);
132         }
133     }
134     int max = b[1];
135     for (int i = 2; i <= array.x; i++)
136     {
137         if (b[i]>max) max = b[i];
138     }
139     cout << "最大联通子数组的和是:" << max << endl;
140     outfile << max;
141 }

运行结果截图：

小组成员：杜文星（http://www.cnblogs.com/duwenxing/p/5360804.html）