題目：HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學寝贡。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負數(shù),是否應該包含某個負數(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一定時最大值
