最大子段求和

3種算法：最大子段求和

一、問題分析

問題：給定有n個整數(可能為負整數)組成的序列 a 1 , a 2 , . . . , a n , a_1,a_2,...,a_n, a1​,a2​,...,an​,求該序列連續的子段和的最大值。 如果該子段的所有元素和是負整數時定義其最大子段和為0。

簡易算法： 兩層循環周遊全部可能值，找出最大的記錄下來。先從 i i i 加到 j j j 如果出現負數，同時記錄目前循環的最大值，并且 j + + j++ j++；然後再 i + + i++ i++ 進行下一趟周遊，找可能的最大值。

分治算法： 在序列中間對問題進行劃分，劃分得到兩段序列；其最大子段和可能出現在三個位置以及求解方法：

1. 出現在左邊 ( l e f t ) (left) (left)子段 ——計算 l e f t left left 到 c e n t e r center center 的最大和，記作 l e f t S u m leftSum leftSum。
2. 出現在右邊 ( r i g h t ) (right) (right)子段 ——計算從 c e n t e r + 1 center+1 center+1 到 r i g h t right right 的最大和，記作 r i g h t S u m rightSum rightSum 。
3. 出現在跨中間 ( c e n t e r center center)子段 —— 從 c e n t e r center center 出發分别向左右擴充，同時記錄分别的 s 1 s_1 s1​ 和 s 2 s_2 s2​ 擴張到值不再增大；這種情況下的值為 c e n t e r S u m = s 1 + s 2 centerSum = s_1+s_2 centerSum=s1​+s2​ 。

此時最大子段和 s u m = m a x ( l e f t S u m , r i g h t S u m , c e n t e r S u m ) sum =max(leftSum,rightSum,centerSum) sum=max(leftSum,rightSum,centerSum) 。

動态規劃算法： 該問題可分為兩個階段：①累加和為負不進行最大和計算，同時将sum值置為0 ②累加和為正時，開始累加。

二、複雜度分析

簡易算法： 兩層 f o r for for 循環需要 O ( n 2 ) O(n^2) O(n2) 的計算時間。

分治算法： 遞歸式

T ( n ) = { O ( 1 ) , n ≤ c 2 T ( n / 2 ) + O ( n ) , n > c T(n)= \begin{cases} O(1),& n\le c \\ 2T(n/2)+O(n) , &n>c \end{cases} T(n)={O(1),2T(n/2)+O(n),​n≤cn>c​

由主函數計算方法可以得到 T ( n ) = O ( n log ⁡ ( n ) ) T(n) = O(n\log(n)) T(n)=O(nlog(n)) 。

動态規劃算法: 明顯隻有一層循環，隻有 O ( n ) O(n) O(n) 的計算時間和空間。

三、程式實作和測試過程和結果

簡易算法：

int sum =0;
        int besti=0;
        int bestj=0;
        for(int i =0;i<n;i++)
        {
            int thissum =0;
            for(int j=i;j <n;j++)
            {
                thissum += a[j];
                if(thissum > sum)
                {
                    sum = thissum;
                    besti = i;
                    bestj = j;
                }
            }
        }
           

分治算法：

int maxSubSum(int left, int right)
{
    int sum =0;
    if(left == right)
        sum = a[left] >0? a[left]:0;  // 問号冒号表達式
    else{
        int center = (left+right)/2;
        int leftsum = maxSubSum(left,center);  // 遞歸求解
        int rightsum = maxSubSum(center+1,right);  // 遞歸求解
        // 向左擴張
        int s1=0;
        int lefts=0;
        for(int i = center;i>=left;i--)
        {
            lefts += a[i];
            if(lefts>s1) s1= lefts;
        }
        // 向右擴張
        int s2 = 0;
        int rights = 0;
        for(int i = center+1;i<=right;i++)
        {
            rights += a[i];
            if(rights>s2) s2= rights;
        }
        sum = s1+s2;
        // 取三種情況的最大值
        if(sum <leftsum) sum = leftsum;
        if(sum <rightsum) sum = rightsum;
    }
    return sum;

}
           

動态規劃算法:

int maxSum()
{
    int sum =0;
    int b=0;
    for(int i=0;i<n;i++)
    {
        if(b>0) b+=a[i];  // 正數則繼續
        else b= a[i];  // 否則直接從下一位開始計算
        if(b>sum) sum=b;
    }
    return sum;
}
           

對檔案資料讀取處理的時間進行統計拟合，發現耗時和預期基本一緻。

四、總結問題

在上圖中雖然不太明顯，但是在動态規劃算法中5000規模的資料那一欄，耗時反而增加，經過多次重複計算，多次采取其他計算方法，仍然出現耗時增加，暫未分析出原因。

另外這個畫圖好麻煩，感覺不會調坐标軸。