問題描述：

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

答案思路（完全沒想到，雖然在往動(dòng)態(tài)規(guī)劃的方向想，但是怎么也沒想到用子數(shù)組的結(jié)束位作為遍歷變量，想過用子數(shù)組的開始為作為遍歷變量，但是怎么也推理不通，笨死啦==）

使用動(dòng)態(tài)規(guī)劃

F（i）：以array[i]為末尾元素的子數(shù)組的和的最大值，子數(shù)組的元素的相對位置不變

F（i）=max（F（i-1）+array[i] ， array[i]）

res：所有子數(shù)組的和的最大值

res=max（res，F(xiàn)（i））

我見其他答案中如下描述，原理一樣但是我想了好久才看懂（...）：

如果當(dāng)前和小于零，那么在進(jìn)行到下一個(gè)元素的時(shí)候，直接把當(dāng)前和賦值為下一個(gè)元素，如果當(dāng)前和大于零，則累加下一個(gè)元素

動(dòng)態(tài)規(guī)劃重要的還是選擇合適的遞推變量。