算法第三章上機實驗報告

1.1 問題描述

題目名稱：

問題描述：給出一組序列，求其連續的一段子序列加起來的和最大，即最大子段和問題。

1.2 算法描述

（1）因為題目要求算法的時間複雜度為o(n)，蠻力枚舉法O(n^3)，優化枚舉法O(n^2)分而治之法O(nlogn)都不可以，是以我們考慮用到動态規劃。

（2）

給出問題表示：Di:以X[i]開頭的最大子數組和

明确原始問題：Smax = max{D[i]},1<=i<=n 

1.3 問題求解：

1.3.1 根據最優子結構性質，列出遞歸方程式。

Di:以X[i]開頭的最大子數組和

初始化：D[n]=X[n]

①當D[i+1]<0時：D[i]=X[i];

②當D[i+1]>0時：  D[i]=X[i]+D[i+1];

1.3.2 給出填表法中表的次元、填表範圍和填表順序。

緯度：一維

填表範圍：1～n

填表順序：從右到左，自底向上

1.3.3 分析該算法的時間和空間複雜度

時間複雜度：O(n)

原因：因為隻使用了一個for循環。

1.3 心得體會（對本次實踐收獲及疑惑進行總結）

2. 你對動态規劃算法的了解和體會

動态規劃算法與分治法類似，都是将問題分解成子問題來求解，不同的是分治法依賴性不強，而動态規劃大規模的最優解是依賴于小規模問題的最優解的。動态規劃算法分為四步：問題結構分析，遞推關系建立，自底向上計算和最優方案追蹤。個人認為最難的是問題結構分析，因為分析不出問題的結構，後續的步驟也難以進行。