【題目】最大連續子數組和（最大子段和）
背景
問題： 給定n個整數（可能為負數）組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。當所給的整數均為負數時定義子段和為0，依此定義，所求的最優值為：Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
例如，當（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)時，最大子段和為20。
-- 引用自《百度百科》具體要求
（1）要求寫出可運行的完整代碼提交至GitHub或者Coding.net系統中，并將代碼地址附到博客內。
（2） 請從語句覆蓋、判定覆蓋、條件覆蓋、判定/條件覆蓋、條件組合覆蓋五個覆蓋標準中，任選一個標準設計測試用例。
（3） 請利用自動測試工具對程序進行測試。
（4） 請將程序運行結果和自動測試分析結果截圖附到博客中。算法與代碼實現
拋棄的算法：通過題目要求，首先想到的是暴力求解，即利用循環，求出每一個子數組的值并進行比較，求出其中子數組的最大值。但是由于此方法效率較低，于是思考下一個方法。
新的算法：我們首先分析出，當子數組和最大時，該子數組的首位和末位（存在的情況下），一定應為正值，且該子數組一定需要大于零才可作為新的最大的子數組并繼續向下運算；否則，我們將拋棄他，并以下一位作為新的運算子數組。我們設每次運算的子數組為ThisSum，新的臨時最大的子數組為MaxSum，根據此特性，可以列出公式：Array[i] = MAX（Array[i-1] + A[i] , A[i]）
根據上述公式，已將具體代碼提交到GitHub上,便不在此贅述，點此查看Github源代碼。
流程圖與測試
根據寫出的代碼，畫出流程圖如下：
為了尋求合適而全面的測試樣例，我找出循環內部的兩條判斷語句的流程，選用判斷條件覆蓋。
線段號 ThisSum>MaxSum ThisSum<0 Blue1 Yes — Yellow2 No Yes Red3 No No 選用的測試樣例數組如下：
數組 備注 Array1：{ } 取邊界值?測試 Array2：{1，-2，3，4，-5} 1->2->1->1->3 Array3：{1，2，3，4，5} 輔助測試 Array4：{-1，-2，-3，-4，-5} 全為負值 故最大為? 根據以上選用的測試樣例，測試結果如下：
Array1：
Array2：
Array3：
Array4：
自動單元測試JUnitTest結果如下:
到此，對最大連續子數組求和的內容結束。
posted @ 2019-04-18 19:27 cocoaman 閱讀(...) 評論(...) 編輯 收藏公告
 - UART寄存器)
)
