HDU1003和HDU1231 , 最大连续序列的和

两道题都是最大连续子序列的和, 都差不多;

虽然好像不只有DP的方法, 不过,这里算是学习DP写的吧;

hdu1003

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100005;
const int INF = 0x3f3f3f3f;
int s[maxn], dp[maxn];

int main(){
    int t, n;
    scanf("%d", &t);
    for(int cas = 1;cas<=t;cas++){
        scanf("%d", &n);
        s[0] = 1;
        for(int i=1;i<=n;i++){
            scanf("%d", &dp[i]);
            s[i] = i;
        }
        for(int i=1;i<=n;i++){
            if(dp[i] + dp[i-1] >= dp[i]){
                dp[i] = dp[i] + dp[i-1];
                s[i] = s[i-1];
            }
        }
        int ans = -INF, st = 1, e = 1;
        for(int i=1;i<=n;i++){
            if(dp[i] > ans){
                ans = dp[i];
                st = s[i];
                e = i;
            }
        }
        printf("Case %d:\n%d %d %d%s\n", cas, ans, st, e, cas<t?"\n":"");
    }
    return 0;
}

hdu1231

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 10005;
const int INF  = 0x3f3f3f3f;
int dp[maxn], a[maxn], s[maxn];

int main(){
    int k;
    while(scanf("%d", &k) == 1 && k != 0){
        bool flag = true;
        for(int i=1;i<=k;i++){
            scanf("%d", &a[i]);
            dp[i] = a[i];
            s[i] = i;
            if(dp[i] >= 0) flag = false;
        }
        s[0] = 1;
        if(flag){
            printf("0 %d %d\n", dp[1], dp[k]);
            continue;
        }
        for(int i=1;i<=k;i++){
            if(dp[i-1] > 0){
                dp[i] = dp[i] + dp[i-1];
                s[i] = s[i-1];
            }
        }
        int ans = -INF, st, e;
        for(int i=1;i<=k;i++){
            if(dp[i] > ans){
                ans = dp[i];
                st = s[i];
                e = i;
            }
        }
        // printf("%d %d\n", st, e);
        printf("%d %d %d\n", ans, a[st], a[e]);
    }
    return 0;
}