問題描述

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

[劍指Offer]連續子數組的最大和

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

算法分析

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

    每一輪循環里，

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

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

電腦資料

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

代碼實現

<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>