題目：傳回一個整數數組中最大子數組的和。
要求：
輸入一個整形數組，數組裡有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間複雜度為O(n)
發表一篇部落格文章講述設計思想，出現的問題，可能的解決方案（多選）、源代碼、結果截圖、總結。
結對開發的夥伴：
部落格名：Mr.缪
姓名：缪金敏
連結：http://www.cnblogs.com/miaojinmin799/
分析：
如果按照最笨的方法就是一個一個的比較先比較一個數的然後二個，直到個數為n為止，但是這樣時間複雜度一算估計得要O(n*n)，是以不可行，後來通過上網查閱，找到了動态規劃方法來實作求最大和，把比較大小分解為一小段一小段，每次比較輸入數和輸入前幾個數之和的大小，選擇最大的。要想輸出子數組，就必須判斷開始下标和結束下标。開始下标的條件：數組第二列的數前一個比現在的小且小于0且第一列的數小于等于第二列。結束下标的條件：目前的算出的最大子數組+輸入的值比下一步的最大值大于或等于，或第二列的數大于等于第一列。
所遇到困難：
開始下标和結束下标考慮過于單一，有些特殊情況沒有考慮到。
結對開發照：
1 //求一維數組的最大子數組 王文奇 缪金敏 2016/3/23
2 #include<iostream>
3 using namespace std;
4
5 int max(int a,int b) //傳回a和b中的最大值
6 {
7 if (a > b)
8 {
9 return a;
10 }
11 else
12 {
13 return b;
14 }
15 }
16
17 int main()
18 {
19 int Array[100];
20 int i = 1;
21 int dynamic_planning[100][2], j, sum;
22 int start = 0; //最大子數組的起始位置
23 int end = 0; //最大子數組的終止位置
24 cout << "請輸入一組一維數組(回車結束)："<<endl;
25 cin >> Array[0];
26 while (cin.get() != '\n') //回車結束
27 {
28 cin >> Array[i++];
29 }
30 //動态規劃數組初始化
31 dynamic_planning[0][0] = 0;
32 dynamic_planning[0][1] = Array[0];
33 for (j = 1; j<i; j++)
34 {
35 dynamic_planning[j][0] = max(dynamic_planning[j - 1][0], dynamic_planning[j - 1][1]);
36 dynamic_planning[j][1] = max(Array[j], (dynamic_planning[j - 1][1] + Array[j]));
37 //開始下标的條件：數組第二列的數前一個比現在的小且小于0且第一列的數小于等于第二列
38 if (dynamic_planning[j - 1][1] < dynamic_planning[j][1] && dynamic_planning[j - 1][1]<0&&dynamic_planning[j][0]<=dynamic_planning[j][1])
39 {
40 start = j;
41 //cout << "start:"<<start << endl;
42 }
43 //結束下标的條件1：目前的算出的最大子數組+輸入的值比下一步的最大值大于或等于
44 if (dynamic_planning[j - 1][1] >= dynamic_planning[j][0])
45 {
46 end = j - 1;
47 //cout << "end:" << end << endl;
48 }
49 //結束下标的條件2：第二列的數大于等于第一列
50 if (dynamic_planning[j][1] >= dynamic_planning[j][0])
51 {
52 end = j;
53 //cout << "end:" << end << endl;
54 }
55
56 }
57 //cout << start << " " << end << endl;
58 sum = max(dynamic_planning[i - 1][0], dynamic_planning[i - 1][1]);
59 cout << "最大的子數組為：" << endl;
60 for (int i = start; i <= end; i++)
61 {
62 cout << Array[i] << " ";
63 }
64 cout << endl;
65 cout << "最大的子數組的和為：" << sum << endl;
66 return 0;
67 } 運作結果截圖：
總結：
這次實驗主要運用了動态規劃的思想，再就是臨界下标的判斷，一定考慮到所有的情況。
項目計劃總結：
時間記入日志：
缺陷記入日志：