問題描述

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

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

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

算法分析

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

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

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

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

電腦資料

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

代碼實現(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>