# HDU 4066. Random Sequence

### Brief description:

… 問隨機數列 {Ai} 的最大絕對子段合。。 (既最大子段和或最小子段和的絕對值中取較大。。) .. .
(。。Ai 取自 {-1, 1}。。。)

### Analysis:

… 分析不能的我。。。只有打表找規律了。。

```const int N = 100;
DB F[N], D[N], G[N], avg;
int A[N], nn, n, m;

int f(){
int res = 0, sum = 0;

REP(i, n){
sum = max(0, sum + A[i]);
checkMax(res, sum);
}

return res;
}

int g(){
int res = 0, sum = 0;

REP(i, n){
sum = max(0, sum - A[i]);
checkMax(res, sum);
}

return res;
}

void dfs(int k = 0){
if (k == n){
avg += max(f(), g());
}
else {
FOR_1_N(A[k], -m, m){
if (A[k])
dfs(k+1);
}
}
}

int main(){

//freopen("in.txt", "r", stdin);

m = 1, nn = 12; FOR_N(n, 1, nn){
avg = 0, dfs(); //avg /= pow(2.0 * m, n);
F[n] = avg;
}

REP(i, nn) D[i] = F[i+1] - F[i];
REP(i, (nn-1)/2) G[i] = D[2*(i+1)] / D[2*i];

printf("F: ");
REP(i, nn){
printf("%.3lf ", F[i]);
}
puts("");

printf("D: ");
REP(i, nn-1){
printf("%.3lf ", D[i]);
}
puts("");

printf("G: ");
REP(i, (nn-1)/2){
printf("%.3lf ", G[i]);
}
}
```
```const int N = 1509;
DB F[N], D[N], G[N];
int nn, n, m;

int main(){

//freopen("in.txt", "r", stdin);

m = 1, nn = 1501;

REP(i, (nn-1)/2){
G[i] = DB (2*i+1) / (2*(i+1));
}

D[0] = 1;
REP(i, nn-1){
D[i+1] = D[i] * G[i/2];
++i, D[i+1] = D[i];
}

F[0] = 0;
REP(i, nn-1){
F[i+1] = F[i] + D[i];
}

REP_C(Case, RD()){
printf("Case %d: %.6lf\n", Case, F[RD()]);
}
}
```

### Further discussion:

。。隨機矩陣的最大子矩陣。。
(這個方向的推廣太複雜了。。先 hold 。。。)
。。。隨機序列的最大子段和。。。
(題目中可以取絕對值的限制太不自然了。。。但是去掉以後完全找不出規律。。