求二维整数数组中最大联通子数组的和

浏览数：43 / 时间：2015年06月11日

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

2 思路：对n*m的二维数组进行分解，分解为n个一维数组，再先求这n个一维数组的最大子数组和，并记下每行最大一维子数组的下标如2-5，这是就会分两种情况第一种是行之间的最大子数组是相连的，如第一行是2-5，第二行是3-6，这是直接相加就行。第二种是不相连的如第一行是2-5，第二行是6-7，这时候就把每行的最大子数组看成一个整体，再使每个最大数组块进行相连，求使其相连的最小代价。最后就可求出最大联通子数组的和。

3 代码

 1 #include<iostream>
 2 using namespace std;
 3 int zuida(int n,int a[],int *sm,int *mm);
 4 
 5 void main()
 6 {
 7     int m,n,i,j,sm,mm,t2;
 8     int sum,max;
 9     int up[100],down[100],t[100];
10     int a[100][100],b[100];
11     cout<<"输入二维数组的行"<<endl;
12     cin>>m;
13      cout<<"输入二维数组的行"<<endl;
14      cin>>n;
15     for(i=0;i<m;i++)
16     {
17         for(j=0;j<n;j++)
18         {
19             cin>>a[i][j];
20         }
21     }
22  
23     for(i=0;i<m;i++)
24     {
25         for(j=0;j<n;j++)
26         {
27             b[j]=a[i][j];
28         }
29         sum=zuida(n,b,&sm,&mm);
30         up[i]=sma;                                   
31         down[i]=mm;
32         t[i]=sum;
33  
34     }
35     t2=t[0];
36     for(i=0;i+1<m;i++)
37     {
38         if(up[i]<=down[i+1] && down[i]>=up[i+1])
39         {
40             t2+=t[i+1];
41         }
42          for(j=up[i];j<up[i+1];j++)
43         {
44             if(a[i+1][j]>0) t2+=a[i+1][j];                   //判别独立正数
45         }
46  
47     }
48      cout<<t2<<endl;
49  
50 }
51 
52 
53 int zuida(int n,int a[],int *sm,int *mm)
54 {
55     int b[100]={0};
56     int i,sum1=0,max1=0;
57     for(i=0;i<n;i++)
58     {
59         if(sum1<0)
60         {
61             sum1=a[i];
62         }
63         else
64         {
65             sum1=sum1+a[i];
66         }
67         b[i]=sum1;
68     }
69     max1=b[0];
70     for(i=0;i<n;i++)
71     {
72         if (max1<b[i])
73          {
74              max1= b[i];
75              *mm = i;
76          }
77     }
78      for (i = *mm;i >= 0;i--)
79     {
80         if (b[i] == a[i])
81         {
82              *sm= i;
83              break;
84         }
85     }
86      return max1;
87 }
88