題目:傳回一個整數數組中最大子數組的和。
要求：
輸入一個整形數組，數組裡有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
如果數組A[0]……A[j-1]首尾相鄰，允許A[i-1]，…… A[n-1]，A[0]……A[j-1]之和最大。
同時傳回最大子數組的位置。
求所有子數組的和的最大值。
結對開發的夥伴：
部落格名：Mr.缪
姓名：缪金敏
連結：http://www.cnblogs.com/miaojinmin799/
分析：這是在第四次程式的基礎上再加了首尾連結，是以我在原先的基礎上把輸入的數組有重新在數組末尾再生成了一遍，在動态規劃外圍再加一個循環，進而實作計算A[0]-A[n]或者A[1]-A[n]-A[0]等等最大值計算，然後用一個數組記錄最大值和還有起始位址和結尾位址。然後輸出子數組。
代碼：
1 //求一維數組的最大子數組2 王文奇 缪金敏 2016/3/26
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[10000];
20 int i = 1;
21 int dynamic_planning[10000][2], j, sum[10000];
22 int start[10000] = { 0 }; //最大子數組的起始位置
23 int end[10000] = { 0 }; //最大子數組的終止位置
24 cout << "請輸入一組一維數組(回車結束)：" << endl;
25 cin >> Array[0];
26 while (cin.get() != '\n') //回車結束
27 {
28 cin >> Array[i++];
29 }
30 for (j = i; j < 2 * i; j++) //數組末尾再生成了一遍
31 {
32 Array[j] = Array[j - i];
33 }
34 int n = 0;
35
36 //動态規劃數組初始化
37 while (true){
38 dynamic_planning[0][0] = 0;
39 dynamic_planning[0][1] = Array[n];
40 for (j = 1; j<i; j++)
41 {
42 dynamic_planning[j][0] = max(dynamic_planning[j - 1][0], dynamic_planning[j - 1][1]);
43 dynamic_planning[j][1] = max(Array[j + n], (dynamic_planning[j - 1][1] + Array[j + n]));
44 //開始下标的條件：數組第二列的數前一個比現在的小且小于0且第一列的數小于等于第二列
45 if (dynamic_planning[j - 1][1] < dynamic_planning[j][1] && dynamic_planning[j - 1][1]<0 && dynamic_planning[j][0] <= dynamic_planning[j][1])
46 {
47 start[n] = j + n;
48 //cout << "start:"<<start << endl;
49 }
50 //結束下标的條件1：目前的算出的最大子數組+輸入的值比下一步的最大值大于或等于
51 if (dynamic_planning[j - 1][1] >= dynamic_planning[j][0])
52 {
53 end[n] = j - 1 + n;
54 //cout << "end:" << end << endl;
55 }
56 //結束下标的條件2：第二列的數大于等于第一列
57 if (dynamic_planning[j][1] >= dynamic_planning[j][0])
58 {
59 end[n] = j + n;
60 //cout << "end:" << end << endl;
61 }
62
63 }
64 sum[n] = max(dynamic_planning[i - 1][0], dynamic_planning[i - 1][1]);
65 n++;
66 if (n == i)
67 {
68 break;
69 }
70 }
71 int max = sum[0];
72 n = 0;
73 for (j = 0; j < i; j++)
74 {
75 if (sum[j]>max)
76 {
77 max = sum[j];
78 n = j;
79 }
80 }
81 cout << "最大的子數組為：" << endl;
82 if (start[n] <= end[n])
83 {
84 for (j = start[n]; j <= end[n]; j++)
85 {
86 cout << Array[j] << " ";
87 }
88 }
89 else
90 {
91 for (j = start[n]; j < i; j++)
92 {
93 cout << Array[j] << " ";
94 }
95 for (j = 0; j <= end[n]; j++)
96 {
97 cout << Array[j] << " ";
98 }
99 }
100 cout << endl;
101 cout << "起始索引： " << start[n];
102 if (end[n] >= i)
103 cout << "終止索引： " << end[n] - i;
104 else
105 cout << "終止索引： " << end[n];
106 cout << endl;
107 //cout << start << " " << end << endl;
108
109 cout << "最大的子數組的和為：" << sum[n] << endl;
110 return 0;
111 } 運作結果截圖：
總結：
這一次練習隻是在上一次基礎上多加了一次循環，是以相對較為簡單。
項目計劃總結：
時間記錄日志：
缺陷記錄日志：