Max Sum（hdu-1003）

Max Sum（hdu-1003）

一道很有意思的dp，說它有意思是因為他的原理其實很簡單，而且掃描一次就可以得到最終的答案。

如果當前這個數之前的和小於0，那麼最大和就從當前的數重新開始；否則最大和就是之前的和加上當前這個數。

這樣為什麼是正確的呢？ 我們假設當前這個數之前的連續和小於0，那麼他對下面的貢獻是負的，所以無論後面的數有多大，最大連續和肯定都不如捨棄前面負貢獻的和大。

然後每次更新dp[i]的最大值，就相當於由枚舉的連續和的終點。

#include
#include
#include
#include
using namespace std;
int T,n,a[100005],dp[100005];
int main(){
    scanf("%d",&T);
    int kase = 0;
    while(T--){
        scanf("%d",&n);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        printf("Case %d:\n",++kase);
        int ans = -1000000000,x1,x2,l,r;
        dp[1] = a[1];
        x1 = 1; ans = dp[1];
        l=1; r=1;
        for(int i=2;i<=n;i++){
            if(dp[i-1]<0) {
                x1 = i;
                dp[i] = a[i];
            } else dp[i] = dp[i-1] + a[i];
            if(ans