最大聯通子數組的和

?在幾次“迭代”開發數組的項目之后老師又布置了這個“聯通數組”的任務，當然，此次任務依舊是“結對編程”，要求如下：

1、題目：返回一個二維數整數組中最大聯通子數組的和；

2、數組中有正數，也有負數；

3、求所有子數組的最大值，要求時間復雜度為O(n)；

4、程序要使用的數組放在input.txt文件中，文件的格式：行數，列數，每一行的元素；

---

?

一、實驗思路?

? ? ? 數組的行和列和數組元素又文件讀入，然后把數按行分成幾個一維數組，對于該一維數組，求出他們的最大連續數組之和，并且記錄下最大連續數組的第一位和最后一位的位置，之后判斷幾個一維數組的最大連續數組的位置是否相接或包括。最后在加上沒有包括的正數（必須在上一行的最大連續數組的第一位和最后一位的位置之間），輸出之前加和。

二、實驗代碼及實現

代碼如下：

1 //2016/4/1 求最大聯通子數組的和——趙子茵&孔宇航 2 3 #include<iostream> 4 #include<fstream> 5 using namespace std; 6 7 int Max(int n, int arr[], int *Start_mark, int *Final_mark) 8 { 9 int step[100] = { 0 };//Step記錄每步計算子數組的和 10 int i, sum = 0, max1 = 0; 11 /* sum是子數組的和 12 max1是子數組最大和 13 */ 14 for (i = 0; i<n; i++) 15 { 16 if (sum<0) 17 sum = arr[i]; 18 else 19 sum = sum + arr[i]; 20 step[i] = sum; 21 } 22 max1 = step[0]; 23 for (i = 0; i<n; i++) 24 { 25 if (max1<step[i]) 26 { 27 max1 = step[i]; 28 *Final_mark = i; 29 } 30 } 31 for (i = *Final_mark; i >= 0; i--) 32 { 33 if (step[i] == arr[i]) 34 { 35 *Start_mark = i; 36 break; 37 } 38 } 39 return max1; 40 } 41 42 void main() 43 { 44 int m, n, i, j, Start_mark, Final_mark, big; 45 int Max1; 46 int read[10000];//讀取文件的字符集 47 int up[100], down[100], h[100]; 48 int Arr2[100][100], Arr1[100]; 49 /* m行n列的數組 50 Start_mark表示最大子數組的起始坐標 51 Final_mark表示最大子數組的終止坐標 52 big表示最后輸出的最大聯通子數組和 53 Max1是函數返回的一維數組最大子數組和 54 up存放每行最大子數組起始坐標 55 down存放每行最大子數組終止坐標 56 h存放每行最大子數組的和 57 Arr2存放二維數組 58 Arr1存放拆成的一維數組 59 */ 60 61 /*cout << "請輸入二維數組的行數和列數："; 62 cin >> m >> n; 63 cout << "請輸入這個二維矩陣：" << endl; 64 for (i = 0; i<m; i++) 65 { 66 for (j = 0; j<n; j++) 67 { 68 cin >> a[i][j]; 69 } 70 }*/ 71 72 //文件輸入 73 ifstream infile("input.txt", ios::in); 74 if (infile.is_open() == false) 75 { 76 cerr << "open error!" << endl; 77 exit(1); 78 } 79 infile >> read[0];//讀取行數m 80 m = read[0]; 81 infile >> read[1];//讀取列數n 82 n = read[1]; 83 cout << "指定文件中" << read[0] << "行 " << read[1] << "列的二維數組如下：" << endl; 84 for (i = 0; i < m; i++)//讀取數組并按格式輸出 85 { 86 for (j = 0; j < n; j++) 87 { 88 infile >> read[i + 2]; 89 Arr2[i][j] = read[i + 2]; 90 cout << Arr2[i][j] << " "; 91 if (j % (n - 1) == 0 && j != 0) 92 //if (j == n-1) 93 cout << endl; 94 } 95 } 96 infile.close(); 97 98 //把二維數組按行分解為幾個一維數組 99 for (i = 0; i<m; i++) 100 { 101 for (j = 0; j<n; j++) 102 { 103 Arr1[j] = Arr2[i][j]; 104 } 105 Max1 = Max(n, Arr1, &Start_mark, &Final_mark); 106 up[i] = Start_mark; 107 down[i] = Final_mark; 108 h[i] = Max1; 109 } 110 111 big = h[0]; 112 for (i = 0; i + 1<m; i++) 113 { 114 if (up[i] <= down[i + 1] && down[i] >= up[i + 1])//聯通，則相加 115 big += h[i + 1]; 116 for (j = up[i]; j<up[i + 1]; j++) 117 { 118 if (Arr2[i + 1][j]>0)//是否獨立正數，有則加 119 big += Arr2[i + 1][j]; 120 } 121 } 122 123 cout << "此二維數組的最大聯通子數組的和為：" << endl; 124 cout << big << endl; 125 126 }

運行結果如下：

? ? ??

? ??

? ? ?

三、實驗心得體會

? ? ??對于本次實驗，我們最開始嘗試過遍歷數組的方法，設置了結構體，將數組的數設置坐標，但是后來沒有掌握好方法以失敗告終。在課堂上受到同學的啟發將二維數組編程一位數組，比如第一行和第二行加和后出現新的一位數組的方法，在網上閱讀了寫別人的思路，最后和小伙伴寫出了這個程序。這個程序存在缺陷，個別的測試用例會出錯，現在的程序只能解決最大連續數組相連的，還不能解決不相連的，對于最后今加上剩余的正數，只會加上與第一行重合的，第三行以及以下的行并不加上前一步加上的第二行的正數。這個缺陷會在以后慢慢完善，希望老師諒解。

最后附 孔同學（孔宇航）博客地址：http://www.cnblogs.com/kongyuhang/

轉載于:https://www.cnblogs.com/2016helen/p/5352919.html

總結

以上是生活随笔為你收集整理的最大联通子数组的和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。