題目描述
HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會后,他又發話了:在古老的一維模式識別中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。給一個數組，返回它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)
解題思路
如果我們有個序列{1,-2,3},顯然最大子序列是{3},如果我們在這個序列后面再加入一個數t，我們怎么去求加入一個數之后新的序列的連續子序列{1，-2，3，t}的最大和？
設以t為序列尾的最大子序列和為sum,則我們可以很直觀地看出sum=max{3+t,t}，這樣理解起來很簡單，因為3就在t前面，而我們已經知道以3為結尾的最大連續子序列和就是3，這個3就是t繞不過去的一個坑。
知道這個關系后我們就可以由題目推出這樣一個式子；
設F[n]為下標為n結尾的連續子序列最大和，數組名為num
推出:F[n]=max{F[n-1]+num[n]}
代碼實現
class Solution {
public:int GetMax(int a,int b){return a>b?a:b;}int FindGreatestSumOfSubArray(vector<int> array) {if(array.empty())return 0;int sum = array[0];int max = array[0];for(int i= 1; i< array.size();++i){max = GetMax(max+array[i],array[i]);sum = GetMax(sum,max);}return sum;}
};
)
)
