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

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length == 0){
            return 0;
        }
        int currSum = array[0];
        int sum = array[0];
        for(int i = 1; i < array.length; i++){
            currSum = currSum >= 0 ? currSum + array[i] : array[i];
            sum = currSum > sum ? currSum : sum;
        }
        return sum;
    }
}

通過一個currSum統(tǒng)計當前正序列能到達的最大值，如果currSum變成了負值說明剛剛那個負數(shù)太小了，以至于把之前辛辛苦苦攢的正值和都給抵消掉了，所以我們不能將這個負數(shù)添加到連續(xù)數(shù)組中，所以連續(xù)子數(shù)組一定在這個數(shù)的后面，我們需要在后面更新這個currSum，所以將currSum置為當前數(shù)，到下一次循環(huán)時，currSum仍然時負的，直到一個正數(shù)出現(xiàn)，我們就可以重新計算這個和了，如果這個currSum大于我們之前訪問的所有的sum，則更新sum為currSum；
最后返回的sum一定時最大值