Russell_0221

   給定n個整數(shù)（可能為負(fù)數(shù)）組成的序列a[1],a[2],a[3],…,a[n]，求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。當(dāng)所給的整數(shù)均為負(fù)數(shù)時，定義子段和為0。

   要求算法的時間復(fù)雜度為O(n)。

#include <iostream>
using namespace std;

int Maxsum(int n, int *a){
    int sum = 0, b=0;
    for(int i=1; i<n; i++){
        if(b>0)
            b += a[i];
        else
            b = a[i];
        if(b>sum)
            sum = b;
    }
    return sum;
}

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    int m = Maxsum(n, a);
    cout<<m;
    return 0;
}

   因?yàn)楫?dāng)所給的整數(shù)均為負(fù)數(shù)時，定義子段和為0，所以需要先判斷所給的整數(shù)的正負(fù)情況。

   一開始 b=0不符合b>0的條件，所以b = a[1] = -2，而-2只會使字段和更小，因此sum不能更新。

   當(dāng)i=2時，b=-2<0，所以b = a[1] =11， 而11>0，所以sum更新為11。

   接下來的判斷方式相同……

4.算法時間及空間復(fù)雜度分析

   時間復(fù)雜度：因?yàn)檠h(huán)了n次，所以時間復(fù)雜度為O(n)。

   空間復(fù)雜度：因?yàn)闆]有其他的數(shù)組，所以空間復(fù)雜度為O(n)。

5.心得體會

   對動態(tài)規(guī)劃掌握不熟練，雖然能夠理解代碼含義，但是對動態(tài)規(guī)劃遞歸式的掌握并不好，不能很清晰地解釋動態(tài)規(guī)劃的表達(dá)式含義及作用。可能需要多花些時間來慢慢理解動態(tài)規(guī)劃。

6.動態(tài)規(guī)劃的個人體會和思考

  動態(tài)規(guī)劃的需要在思考時思路清晰，邏輯暢通，不然可能會被繞進(jìn)去。動態(tài)規(guī)劃問題中前后鏈接緊密，需要找到其中的共同點(diǎn)并寫出動態(tài)規(guī)劃遞歸式來幫助解答問題。不同的構(gòu)造方法也會導(dǎo)致空間或時間復(fù)雜度的不同。