一、什么是求最大連續(xù)子數(shù)列和

首先來看看這是個(gè)怎樣的問題的，問題描述：一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和，求所有子數(shù)組的和的最大值。注意：當(dāng)全是負(fù)數(shù)的情況時(shí)，返回最大的那個(gè)負(fù)數(shù)

二、解題思路

這個(gè)問題的思路其實(shí)非常簡單，從左到右掃描數(shù)組，在掃描過程中，記錄數(shù)組的負(fù)數(shù)的個(gè)數(shù)和掃描過中數(shù)據(jù)中的最大值，并累加每個(gè)掃描到的數(shù)據(jù)的和，假設(shè)用變量thisSum（初值為0）保存，如果當(dāng)前的累加值大于之前的累加值的最大值 （例如用變量sum記錄，初值為0），則把當(dāng)前的最大值保存為最大值（sum = thisSum），如果thisSum小于0，則把thisSum設(shè)置為0并重新進(jìn)行累加。一直這樣掃描數(shù)組，直到把數(shù)組掃描完。

由于thisSum已經(jīng)小于0，也就是說之前統(tǒng)計(jì)的和可以舍棄，因?yàn)榘旬?dāng)前的元素累加之后，結(jié)果反而小了。例如把數(shù)組分成兩部分AB，因?yàn)锳的值小于0，所以如果從B開始從新累加，則其值一定比包括A然后去累加B的結(jié)果大，因?yàn)锳小于0.

由于如果數(shù)組全是負(fù)數(shù)時(shí)，要返回最大的負(fù)數(shù)，而從上面所說的說法中，我們可以看到當(dāng)前累加總和（thisSum）總是與0進(jìn)行比較，如果小于0則把thisSum置為0，所以當(dāng)數(shù)組全是負(fù)數(shù)時(shí)，thisSum和數(shù)組的最大子序列之和（sum）總是為0，而與現(xiàn)實(shí)有點(diǎn)不一樣，所以就要記錄負(fù)數(shù)的數(shù)量，當(dāng)負(fù)數(shù)的數(shù)量等于元素的個(gè)數(shù)（即全是負(fù)數(shù)）時(shí)，就要把最大連續(xù)子序列和置為最大的負(fù)數(shù)。這也是前面所說的，在掃描過程中記錄負(fù)數(shù)的個(gè)數(shù)和最大元素的作用。

三、實(shí)現(xiàn)代碼

?

    int MaxSum(int* a,int n)

{

    int sum = 0; //用于記錄最大的連續(xù)子數(shù)組和

    int flag = 0;//用于記錄負(fù)數(shù)的個(gè)數(shù)

    int MaxNum = *a;//用于記錄數(shù)組中最大的數(shù)

    int ThisSum = 0;//用于記錄當(dāng)前的連續(xù)子數(shù)組和

    for(int i = 0; i < n; ++i)

    {

        if(a[i] < 0) //如果無素為負(fù)數(shù)，則把flag的值加1

            ++flag;

        if(MaxNum < a[i]) //記錄數(shù)組當(dāng)前的最大值

            MaxNum = a[i];

        ThisSum += a[i]; //累加更新當(dāng)前的子數(shù)組之和

        if(ThisSum > sum)

        {

            //若當(dāng)前連續(xù)子數(shù)組之和大于記錄的子數(shù)組之和

            //則設(shè)置最大連續(xù)子數(shù)組之和為當(dāng)前的和

            sum = ThisSum;

        }

        else if(ThisSum < 0)

        {

            //如果當(dāng)前連續(xù)子數(shù)組之和小于0，則拋棄之前的連續(xù)子數(shù)組，

            //從此元素的下一個(gè)元素重新計(jì)算連續(xù)子數(shù)組之和

            ThisSum = 0;

        }

    }

    //若全是負(fù)數(shù)，最大值為數(shù)組中的最大無素

    if(flag == n)

        sum = MaxNum;

    return sum;

}
  

我們?cè)賮砜纯礈y(cè)試結(jié)果吧，測(cè)試代碼如下：

?

?

    int main()

{

    int a[100] = {1, -2, 3, 10, -4, 7, 2, -5};

    cout<<MaxSum(a,8)<<endl;

    return 0;

}
  

運(yùn)行結(jié)果如下：

?

從運(yùn)行結(jié)果和測(cè)試數(shù)據(jù)來看，最大的連續(xù)子數(shù)組應(yīng)該是3，10，-4，7，2.它們的和就為18.

四、時(shí)間復(fù)雜度和空間復(fù)雜度分析

從代碼和上面的解說可以看到，這個(gè)算法的時(shí)間復(fù)雜度只為O(N)，而且常數(shù)為1，即只需要掃描一次數(shù)組即可完成任務(wù)。而且用到的輔助空間也非常少，只有四個(gè)變量，空間復(fù)雜度為O(1)。

五、完整代碼代碼下載地址：

https://github.com/ljianhui/Arithmetic

文件名： max_sum_of_continuous_sub_array.cpp

?

求最大連續(xù)子數(shù)列和（只掃描一次數(shù)列）