### 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 。。。)

。。。随机序列的最大子段和。。。

(题目中可以取绝对值的限制太不自然了。。。但是去掉以后完全找不出规律。。

对数组的取值范围进行推广, {-m <= x <= m, x != 0, x 是整数}。。。
(后两个限制去掉后也变成了完全不同的问题。。)
两个弱化。。
。。只考虑前缀和 (partial sums)。。。
。。只考虑单个项目的最大值。。。

### External link:

http://acm.hdu.edu.cn/showproblem.php?pid=4066

http://math.stackexchange.com/questions/139159/the-length-of-maximum-subsequence-in-a-random-sequence