HDU1003 Max Sum && HDU1024 Max Sum Plus Plus

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1003

1003是喜聞樂見的最大連續子串和，經典的動态規劃題目，經典歸經典，我确實是剛剛做……在這道題中，我們需要保證的是在計算過程之中，計算的和是一直增加的，如果碰到了讓和減少的元素，直接把和更新為0，并且更新臨時首指針，每找到一個更優的解，把真正的首指針和尾指針更新，整個過程中一直保證的是和是遞增的。注意我說的是非全負的情況。

#include <cstdio>
int sum, s, t, ss, maxn, a[100100];
bool f;
int main(){
    int t, n, p;
    scanf("%d", &p);
    for (int k = 1; k <= p; k++){
        scanf("%d", &n);
        f = 0, maxn = -9999999; sum = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            if (a[i] >= 0) f = 1;
        }
        if (!f){
            for (int i = 1; i <= n; i++)
              if (a[i] > maxn){
                  maxn = a[i];
                  s = i;
              }
            printf("Case %d:\n%d %d %d\n", k, maxn, s, s);
        }
        else{
            s = 1; t = 1; ss = 0;
            for (int i = 1; i <= n; i++){
                sum += a[i];
                if (sum < 0){
                    ss = i;
                    sum = 0;
                }
                else if (sum > maxn){
                    maxn = sum;
                    s = ss + 1;
                    t = i;
                }
            }
            printf("Case %d:\n%d %d %d\n", k, maxn, s, t);
        }
        if (k < p) printf("\n");
    }
    return 0;
}
           

題目連結： http://acm.hdu.edu.cn/showproblem.php?pid=1024

這道題厲害了，要求在n個數裡面求m個最大子段和，要求最終的和最大，其實就是計算m次，因為這此不用記錄區間的首尾元素，是以其實比上一道題好寫一些。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000100;
int n, m, ans, a[maxn], f[maxn], g[maxn];
int main(){
    while (~scanf("%d%d", &m, &n)){
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= m; i++){
            ans = -100 * maxn;
            for (int j = i; j <= n; j++){
                f[j] = max(f[j - 1], g[j - 1]) + a[j];
                g[j - 1] = ans;
                ans = max(ans, f[j]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}