問題描述

    HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機(jī)專業(yè)的同學(xué)，

[劍指Offer]連續(xù)子數(shù)組的最大和

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

算法分析

    有一個temp用于探路，sum負(fù)責(zé)保存最終值，初始都為數(shù)組第一個數(shù)；

    每一輪循環(huán)里，

    temp如果小于0，則temp為當(dāng)前數(shù)；否則temp等于temp加上當(dāng)前數(shù)；

    然后比較sum和temp的大小，sum等于大的那個，

電腦資料

《[劍指Offer]連續(xù)子數(shù)組的最大和》(http://www.szmdbiao.com)。

代碼實現(xiàn)

<code class="hljs" cpp="">class Solution {public:    int FindGreatestSumOfSubArray(vector<int>array) {         if(array.size()==0) return 0;         int sum = array[0];         int temp = array[0];         for(int i=1;i</int></code>