467
技術社區[雲棲]
動態規劃-循環數組的最大子數組和
jobdu----題目1527：首尾相連數組的最大子數組和
時間限製：1 秒內存限製：128 兆特殊判題：否提交：1769
解決：335
題目描述：
給定一個由N個整數元素組成的數組arr，數組中有正數也有負數，這個數組不是一般的數組，其首尾是相連的。數組中一個或多個連續元素可以組成一個子數組，其中存在這樣的子數組arr[i],…arr[n-1],arr[0],…,arr[j]，現在請你這個ACM_Lover用一個最高效的方法幫忙找出所有連續子數組和的最大值（如果數組中的元素全部為負數，則最大和為0，即一個也沒有選）。
輸入：
輸入包含多個測試用例，每個測試用例共有兩行，第一行是一個整數n（1=<n<=100000），表示數組的長度，第二行依次輸入n個整數（整數絕對值不大於1000）。
輸出：
對於每個測試用例，請輸出子數組和的最大值。
樣例輸入：
6
1 -2 3 5 -1 2
5
6 -1 5 4 -7
樣例輸出：
10
14
來源：
淘寶2013年校園招聘一麵麵試題
思路：
符合條件的連續子數組必然首末元素都為正。所以用tmp表示當前連續子數組之和。若tmp為正，令tmp+=a[i]。若為負，tmp=a[i]。tmp所取過的最大值就是最大連續子數組和ans_1。
此題創新之處在於數組視為循環的，首尾可以拚接。什麼情況下符合條件的子數組需要首尾相連呢——————中間有一段連續子數組，其和為負且絕對值較大。
故我們對a[ ]每個元素改變符號後再求最大連續子數組和ans_2。
sum為數組每個元素的和。
原數組去掉中間這段子數組後的值為sum+ans_2。
最後答案為max(sum+ans_2,ans_1);
代碼
最後更新：2017-04-03 12:55:35