|
%I #25 Dec 16 2017 18:10:37
%S 1,4,11,27,63,142,314,684,1474,3150,6685,14110,29640,62022,129337,
%T 268930,557752,1154164,2383587,4913835,10113983,20787252,42668775,
%U 87479539,179157497,366547820,749256450,1530251194,3122882776,6368433118,12978230568,26431617730,53799078716,109442256914,222519713892,452208698216,918560947022,1865036287632,3785181059505,7679199158098
%N Sum of maximum subrange sum over all length-n arrays of {1, -1}.
%C The maximum subrange sum of an array x = x[1..n] is the maximum possible value of the sum of the entries in x[a..b] for 1 <= a <= b <= n. The empty subrange has sum 0 and is also allowed. For example, the maximum subrange sum of (-1,1,1,1,-1,-1,1, 1, 1, -1) is 4.
%C Thus a(n)/2^n is the expected value of the maximum subrange sum. Heuristically this expected value should be approximately sqrt(n), but I don't have a rigorous proof.
%H Joerg Arndt, <a href="http://jjj.de/fxt/demo/seq/#A276691">C++ program for this sequence</a>, (2016)
%H Jon Bentley, <a href="http://dx.doi.org/10.1145/358234.381162">Programming pearls: algorithm design techniques</a>, Communications of the ACM, (1984) 27 (9): 865-873.
%H <a href="https://www.quora.com/What-is-the-expected-value-of-the-sum-of-the-maximum-sum-subvector-if-the-arrays-elements-are-random-real-numbers-chosen-uniformly-from-1-1">discussion on Quora</a> (not all comments there are correct)
%e For n = 3, the maximum subrange sum of (-1,-1,-1) is 0 (the empty subrange); for (1 1 -1) and (-1 1 1) it is 2; for (1 1 1) it is 3; and for the 4 remaining arrays of length 3 it is 1.
%e Thus the sum is 3+(2*2)+4*1 = 11.
%o (MATLAB)
%o for n = 1:23
%o L = 2*(dec2bin(0:2^n-1)-'0')-1;
%o S = L * triu(ones(n,n+1),1);
%o R = max(S,[],2);
%o for i = 1:n
%o R = max(R, max(S(:,i+1:n+1),[],2) - S(:,i));
%o end
%o A(n) = sum(R);
%o end
%o A % _Robert Israel_, Sep 13 2016
%Y Cf. A272604.
%K nonn
%O 1,2
%A _Jeffrey Shallit_, Sep 13 2016
%E a(20)-a(23) from _Robert Israel_, Sep 13 2016
%E a(24)-a(32) from _Joerg Arndt_, Sep 14 2016
%E a(33)-a(40) from _Joerg Arndt_, Sep 16 2016
|
