題目描述
HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學(xué)。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當向量全為正數(shù)的時候,問題很好解決太援。但是,如果向量中包含負數(shù),是否應(yīng)該包含某個負數(shù),并期望旁邊的正數(shù)會彌補它呢鼓寺？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)憎亚。給一個數(shù)組茶袒，返回它的最大連續(xù)子序列的和划鸽，你會不會被他忽悠兹吆蕖尽棕？(子向量的長度至少是1)
思路：采用動態(tài)規(guī)劃的思路喳挑。
- 首先仔細觀察數(shù)組的規(guī)律，可以得到下列動態(tài)規(guī)劃的式子：
（1）如果i==0 或者 F[i-1]<=0 那么 F[i] = A[i]
（2）如果i!=0 并且 F[i-1]>0 那么 F[i] = F[i-1] + A[i]
# -*- coding:utf-8 -*-
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
# #動態(tài)規(guī)劃的思想
# #res存儲歷史之和的最大值
res = array[0]
sum = res
for i in range(1,len(array)):
if sum>0:
sum = sum + array[i]
else:
sum = array[i]
#這一步很關(guān)鍵滔悉，不要忘記
if sum>res:
res = sum
return res
s = Solution()
print s.FindGreatestSumOfSubArray([1,-2,3,10,-4,7,2,-5])
