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