数组问题（三）求二维整形数组最大联通子数组的和

本次实验相较于上次求最大子矩阵的和思想还是需要将二维转化为一维还是需要知道每一行的最大子数组

所以我们将问题分解并分析，可以想到先求各行中的最大子数组，并记录下标，求完之后再将各行的最大子数组的下标进行比较可以得到两种情况

1.上一行的最大子数组下标范围和下一行的最大子数组下标范围有重合的部分。

2.上一行的最大子数组下标范围和下一行的最大子数组下标范围无重合的部分。

代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int calculate(int n,int a[],int &sm,int &mm)
 5 {
 6     int b[100]={0};
 7     int i,sum1=0,max1=0;
 8     for(i=0;i<n;i++)
 9     {
10         if(sum1<0)
11         {
12             sum1=a[i];
13         }
14         else
15         {
16             sum1=sum1+a[i];
17         }
18         b[i]=sum1;
19     }
20     max1=b[0];
21     for(i=0;i<n;i++)
22     {
23         if (max1<b[i])
24          {
25              max1= b[i];
26              mm = i;
27          }
28     }
29      for (i = mm;i >= 0;i--)
30     {
31         if (b[i] == a[i])
32         {
33              sm= i;
34              break;
35         }
36     }
37      return max1;
38 }
39 
40 int main()
41 {
42     int row,line,sm,mm,t2,sum,max;
43     int up[10],down[10],t[10],b[10];
44     cout<<"输入数组的行: ";
45     cin>>row;
46     cout<<"输入数组的列: ";
47     cin>>line;
48     int **a;
49     a = new int*[row];
50     for(int i=0; i<row;i++)
51     {
52         a[i] = new int [line];
53     }
54 
55     cout<<"请输入数组元素："<<endl;
56     for(int i=0;i<row;i++)
57     {
58         for(int j=0;j<line;j++)
59         {
60             cin>>a[i][j];
61         }
62     }
63  
64     for(int i=0;i<row;i++)
65     {
66         for(int j=0;j<line;j++)
67         {
68             b[j]=a[i][j];
69         }
70         sum=calculate(line,b,sm,mm);
71         up[i]=sm;                                   
72         down[i]=mm;
73         t[i]=sum;
74  
75     }
76     t2=t[0];
77     for(int i=0;i+1<row;i++)
78     {
79         if(up[i]<=down[i+1] && down[i]>=up[i+1])
80         {
81             t2+=t[i+1];
82         }
83          for(int j=up[i];j<up[i+1];j++)
84         {
85             if(a[i+1][j]>0)
86             {
87                 t2+=a[i+1][j];
88             }
89         }
90     }
91     cout<<"最大联通子数组的和是："<<t2<<endl;
92     for(int i=0;i<row;i++)
93     {
94         delete [] a[i];
95     }
96     delete [] a;
97     system("pause");
98     return 0;
99 }

组员：罗元浩赵承圣（http://www.cnblogs.com/zzcs/）