Happy Birthday！LevOJ P1268 连续子段的最大和

思路：

设 dp[i] 为前以第 i 个数字结尾的连续字段最大和，则有

​ $dp[i]=max(num[i],dp[i-1]+num[i])$

注意， dp[n] 并不能代表整段的连续字段最大和，只能表示以 i 为结尾的连续字段最大和。因此处理完第 i 个数字，将 dp[i] 与历史最大值比较，输出历史最大值即可。

时间复杂度 O(n)

AC代码：

#include<bits/stdc++.h>

using namespace std;

int num[10005];
int dp[10005];

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int ans=-60000;
        dp[1]=a[1];
        for(int i=2;i<=n;i++){
            dp[i]=max(num[i],dp[i-1]+num[i]);
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}