HDU1231 最大連續子序列

PS： 和hdu1003類似。

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x7ffffff;
const int maxn = 100010;

int d[maxn];
int x[maxn];
int n;
void dp()
{
    int idx;
    int st, endx;
    int maxv = -INF;
    memset(x, 0, sizeof(x));
    for(int i = 1; i <= n; i++) {
        if(i==1) x[i] = d[i];
        else {
            x[i] = max(d[i], x[i-1]+d[i]);
        }
        if(x[i] > maxv) {
            maxv = x[i];
            idx = i;
            endx = i;
        }
    }
    st = endx;
    for(int i = idx-1; i >= 1; i--) {
        if(x[i] >= 0)  {
            st = i;
        }
        else break;
    }
    if(maxv < 0) {
        printf("0 %d %d\n", d[1], d[n]);
    } else {
        printf("%d %d %d\n", maxv, d[st], d[endx]);
    }

}

int main()
{
    while(scanf("%d", &n)!=EOF && n) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &d[i]);
        }
        dp();
    }
    return 0;
}