二维数组的最大联通数组

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

设计思路：把数按行分成几个一维数组，对于该一维数组，求出他们的最大连续数组之和，并且记录下最大连续数组的第一位和最后一位的位置，之后判断几个一维数组的最大连续数组的位置是否相接或包括，最后在加上没有包括的正数，输出之前之和就行。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int zuida(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 void main()
41 {
42     int m, n, i, j, sm, mm, t2;
43     int sum, max;
44     int up[100], down[100], t[100];
45     int a[100][100], b[100];
46     cout << "输入二维数组的行和列";
47     cin >> m >> n;
48     cout << "输入二维数组："<<endl;
49     for (i = 0; i<m; i++)
50     {
51         for (j = 0; j<n; j++)
52         {
53             cin >> a[i][j];
54         }
55     }
56 
57     for (i = 0; i<m; i++)
58     {
59         for (j = 0; j<n; j++)
60         {
61             b[j] = a[i][j];
62         }
63         sum = zuida(n, b, &sm, &mm);//调用函数
64         up[i] = sm;
65         down[i] = mm;
66         t[i] = sum;
67 
68     }
69     t2 = t[0];
70     for (i = 0; i + 1<m; i++)
71     {
72         if (up[i] <= down[i + 1] && down[i] >= up[i + 1])
73         {
74             t2 += t[i + 1];
75         }
76         for (j = up[i]; j<up[i + 1]; j++)
77         {
78             if (a[i + 1][j]>0) t2 += a[i + 1][j];                   //判别独立正数
79         }
80 
81     }
82     cout << t2 << endl;
83 
84 }