寫在前沿：本文代碼均使用C語言編寫
Description:
給定一個整數(shù)數(shù)組 nums 罚随，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）羔味，返回其最大和贪嫂。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大田柔，為 6全景。
進階:
如果你已經(jīng)實現(xiàn)復雜度為 O(n) 的解法耀石，嘗試使用更為精妙的分治法求解。
Analysis：
考慮到任何一個數(shù)加上一個負數(shù)的值爸黄，結果都是要小于原數(shù)滞伟。對于一串序列相加，當前面n個數(shù)相加的和sum(n)小于0時炕贵，第n+1個數(shù)加上sum(n)的結果一定是小于第n+1個數(shù)梆奈，因此可以舍棄sum(n)，直接從第n+1個數(shù)重新開始計算序列和称开，這種方法也是屬于動態(tài)規(guī)劃的一類亩钟。每做一次序列的求和，就對結果做一次判斷鳖轰，并把較大的結果存下來清酥，得到序列最大的結果。
完整C代碼：
1蕴侣、原始版本：60ms執(zhí)行用時焰轻。
int maxSubArray(int* nums, int numsSize) {
? ? int temp=0,sum=nums[0];
? ? for(int i=0;i<numsSize;i++){
? ? ? ? if(temp<0)temp=0;
? ? ? ? temp+=nums[i];
? ? ? ? if(temp>sum)sum=temp;
? ? }
? ? return sum;
}
2、修改版本：16ms執(zhí)行用時昆雀。
int maxSubArray(int* nums, int numsSize) {
? ? int temp=nums[0],sum=nums[0];
? ? for(int i=1;i<numsSize;i++){
? ? ? ? if(temp<0)
? ? ? ? ? ? temp=nums[i];
? ? ? ? else
? ? ? ? ? ? temp+=nums[i];
? ? ? ? if(temp>sum)sum=temp;
? ? }
? ? return sum;
}
