算法分析與設計——最大子段和（動态規劃）

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

要求算法的時間複雜度為O(n)。

輸入格式:

輸入有兩行：

第一行是n值（1<=n<=10000)；

第二行是n個整數。

輸出格式:

輸出最大子段和。

輸入樣例:

在這裡給出一組輸入。例如：

6

-2  11  -4  13  -5  -2

輸出樣例:

在這裡給出相應的輸出。例如：

20

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

題目要求時間複雜度為O(n)，是以隻能用一層循環。

#include<iostream>
using namespace std;
int main(){
    int n,now = 0,max = 0;
    cin>>n;
    int *a = new int[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){ //now記錄該數組的累加和，作為是否進行最大和計算的标志
        if(now<=0){ //标志為負，不算進最大子段和中
            now = a[i]; 
        }else { //标志為正，進行子段和累加，求目前子段最大和
            now += a[i]; 
        }
        if(max<now){ //max記錄最大子段和
            max = now;
        }
    }
    cout<<max<<endl;
    return 0;
}