Lintcode 42. 最大子數組的和

Lintcode的第42題最大子數組的和這道題開始的時候會讓人會想的很多感覺沒有解決問題的思路很容易寫出循環嵌套的暴力解題的算法，其實簡單的想想這個問題是很容易解決的。

首先將數組分成兩類：1包含正數的數組2不包含整數的數組。

對於包含正數的數組的處理比較複雜，咱們這裡先不說線索對於不包含正數的數組的處理：

不包含正數的數組

數組不包含正數的解題思路是獲取整個數組中的最大值並返回最大值就可以了，所以對於不包含正數的數組就是找到最大值的問題。

對於包含正數的數組：

咱們先看一下這個數組[2,-2,4,5,-17,5,10,18,-12];

這個數組應該是最具有代表性的數組，咱們的解題思路是：

（1）獲取此數之前最大的累加和，對於累加和為負值或者為0的進行拋棄設置累加值為0，對於是正值更新累加和。

（2）判斷當前累加和是否大於之前存儲的最大值，對於累加和大於最大值的進行更新最大值。

（3）循環執行上述步驟至數組結束。

所以上面的過程簡述為：

（1）輸入數據2，當前累加值為0，累加後為2，當前最大值為0，更新最大值為2

（2）輸入數據-2，當前累加值為2，累加後為0，進行拋棄，累加值為0，當前最大值為2，保持最大值為2

（3）輸入數據4，當前累加值為0，累加後為4，當前最大值為2，更新最大值為4

（4）輸入數據5，當前累加值為4，累加後為9，當前最大值為4，更新最大值為9

（5）輸入數據-17，當前累加值為9，累加後為-8，進行拋棄，設置累加值為0，當前最大值為9，保持最大值9。

（6）輸入數據5，當前累加值為5，累加後為5，當前最大值為9，保持最大值為9.

（7）輸入數據10，當前累加值為5，累加後為15，當前最大值為9，更新最大值為15.

（8）輸入數據18，當前累加值為15，累加後為33，當前最大值為15，更新最大值為33.

（9）輸入數據-12，當前累加值為33，累加後為21，當前最大值為33，保持最大值為33

（10）結束返回最大值為33

程序為：

int maxSubArray(vector &nums) {
 int i=0;
 int max=0;
 int sum=0;
 int data=nums.at(0);
 for(i=0;i<nums.size> {
 sum+=nums.at(i);
 if(data<nums.at> {
 data=nums.at(i);
 }
 if(sum<0)
 {
 sum=0;
 }
 else
 {
 if(sum>max)
 {
 max=sum;
 }
 }
 }
 if(data<0)
 {
 max=data;
 } 
 return max;
 }

/<nums.at>/<nums.size>