題目：

在古老的一維模式識別中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。

思路：

保存兩個值：當前和sum、最大和max。當sum小于等于0時，置sum為當前值；否則將當前值加到sum上。每次sum和max比較，更新max。

另外，動態規劃的思路代碼和這里一樣。動態規劃就是考慮 f(i) 和 f(i-1) 之間的關系。

注意：

需要注意的就是，sum和max初始值的設定，特別是max的初始值。max初始值不能設置為0，因為輸入可能全為負數，應該是 int 的最小值 0x80000000。或者將sum和max初始化為下標為0的元素的值。

另外，需要判斷輸入數組的個數。

代碼：

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

?

轉載于:https://www.cnblogs.com/buxizhizhou/p/4722354.html

總結

以上是生活随笔為你收集整理的【剑指offer】面试题31：连续子数组的最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。