A276691 - OEIS

%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