HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學(xué)。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個負(fù)數(shù),并期望旁邊的正數(shù)會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)。你會不會被他忽悠住？

一種思路，使用兩個循環(huán)，分別計算從開始s到結(jié)束e的和，找出最大的數(shù)，但是這種解法的時間復(fù)雜度為n*n，不建議。

另一種思路，遍歷一次，當(dāng)前的和小于0時拋棄，因為負(fù)數(shù)不管加什么數(shù)，都是變小的，因此重新計算就可以了。