最大數組連續子向量的最大和

最近研究最大數組，稍微總結一下，以後繼續補充：

    标題：

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

    For example, given the array <code>[−2,1,−3,4,−1,2,1,−5,4]</code>,

the contiguous subarray <code>[4,−1,2,1]</code> has the largest sum = <code>6</code>.

    分析：利用掃描算法，從數組最左端開始掃描，一直到最右端，并記下所碰到的最大總和子向量。最大總和的初值為0.

    對于前m個元素，最大總和子數組要麼在前m-1個元素中，要麼是其結束位置為m。

    每日一道理

春蠶死去了，但留下了華貴絲綢；蝴蝶死去了，但留下了漂亮的衣裳；畫眉飛去了，但留下了美妙的歌聲；花朵凋謝了，但留下了縷縷幽香；蠟燭燃盡了，但留下一片光明；雷雨過去了，但留下了七彩霓虹。

    還需注意的一種情況是若所有的元素都為負值，則問題轉化為求數組中的最大數。

    代碼如下：

    int max(int l,int r)

    {

        return (l&gt;r)?l:r;

    }

    int maxSubArray(int A[], int n)

        int TempMax=0,Maxending=0,negative=A[0];

        for(int i=0;i&lt;n;i++)

        {

            Maxending = max(Maxending+A[i],0);

            TempMax = max(TempMax,Maxending);

            if(A[i]&gt;negative)negative=A[i];

        }

        if(negative&lt;0)return negative;

        else return TempMax;

文章結束給大家分享下程式員的一些笑話語錄：

聯想——對内高價，補貼對外傾銷的偉大“民族”企業。