《leetCode》：Maximum Subarray

題目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−,,−,,−,,,−,],
the contiguous subarray [,−,,] has the largest sum = 
           

題目大意：求出連續的子數組的最大和。

思路

此題比較簡單，用一個長度可變的窗來模拟這個過程。當窗覆寫的連續的子數組和大于零，則繼續将該窗的長度向右拉伸一個機關長度，計算此時的子數組和是否大于零。如果仍然大于零，則繼續這樣的操作。如果小于零。則舍棄前面的元素重新開始累加。值得注意的是：要始終将窗中覆寫的連續子數組和與max進行比較，對max進行更新。

int maxSubArray(int* nums, int numsSize) {
    if(nums==NULL||numsSize<){
        return ;
    }
    int max=nums[];//用來儲存最大值。
    int tempSum=;
    for(int i=;i<numsSize;i++){
        tempSum+=nums[i];
        if(tempSum>max){//隻要大于max，則更新
            max=tempSum;
        }
        if(tempSum<){//當此時的和為負數是時，則需要截斷視窗，重新開始累加
            tempSum=;
            continue;
        }
    }
    return max;   
}
           

AC結果如下：

擴充

上面隻要求我們傳回最大的子數組和，這裡我們加一個條件，傳回這個子數組在數組中的起點和終點下标？？

這時候應該怎麼樣來實作了？？？

我相信《leetCode》下一題一定會要求我們這樣來進行求解。但是，看了看，沒有這個題也，不過這個題在《劍指Offer》上面出現過，具體如何來做，可以看以前的這篇博文：http://blog.csdn.net/u010412719/article/details/49052665