題目描述 [連續(xù)子數(shù)組的最大和]
HZ偶爾會(huì)拿些專業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)瘦癌。今天測(cè)試組開完會(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è)開始,到第3個(gè)為止)砚作。給一個(gè)數(shù)組纬纪，返回它的最大連續(xù)子序列的和斤吐，你會(huì)不會(huì)被他忽悠自浦妄？(子向量的長(zhǎng)度至少是1)
解題思路
- 令temp為當(dāng)前最大數(shù)組的和尼摹，num_max為最后返回的最大數(shù)組和
- 從前往后掃描，對(duì)于第i個(gè)元素有兩種選擇：加入前面找到的子數(shù)組剂娄，作為新數(shù)組的第一個(gè)元素
- 如果temp+a[i] > a[i],則令temp=temp+a[i];
- 否則為temp重新賦值蠢涝，temp=a[i]；
- 比較當(dāng)前最大數(shù)值和與最大數(shù)組和
即：
temp = max(temp+a[i], a[i]);
num_max = max(num_max, temp);
代碼
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int num_max = INT_MIN;
int temp = 0;
for(int i=0;i<array.size();i++){
temp = max(array[i], array[i]+temp);
num_max = max(num_max, temp);
}
return num_max;
}
};
