問(wèn)題描述

    HZ偶爾會(huì)拿些專(zhuān)業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專(zhuān)業(yè)的同學(xué)，

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

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

算法分析

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

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

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

    然后比較sum和temp的大小，sum等于大的那個(gè)，

電腦資料

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

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