cp's OEIS Frontend

A276691 Sum of maximum subrange sum over all length-n arrays of {1, -1}.

%I A276691 #25 Dec 16 2017 18:10:37
%S A276691 1,4,11,27,63,142,314,684,1474,3150,6685,14110,29640,62022,129337,
%T A276691 268930,557752,1154164,2383587,4913835,10113983,20787252,42668775,
%U A276691 87479539,179157497,366547820,749256450,1530251194,3122882776,6368433118,12978230568,26431617730,53799078716,109442256914,222519713892,452208698216,918560947022,1865036287632,3785181059505,7679199158098
%N A276691 Sum of maximum subrange sum over all length-n arrays of {1, -1}.
%C A276691 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 A276691 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 A276691 Joerg Arndt, <a href="http://jjj.de/fxt/demo/seq/#A276691">C++ program for this sequence</a>, (2016)
%H A276691 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 A276691 <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 A276691 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 A276691 Thus the sum is 3+(2*2)+4*1 = 11.
%o A276691 (MATLAB)
%o A276691 for n = 1:23
%o A276691   L = 2*(dec2bin(0:2^n-1)-'0')-1;
%o A276691   S = L * triu(ones(n,n+1),1);
%o A276691   R = max(S,[],2);
%o A276691   for i = 1:n
%o A276691     R = max(R, max(S(:,i+1:n+1),[],2) - S(:,i));
%o A276691   end
%o A276691   A(n) = sum(R);
%o A276691 end
%o A276691 A  % _Robert Israel_, Sep 13 2016
%Y A276691 Cf. A272604.
%K A276691 nonn
%O A276691 1,2
%A A276691 _Jeffrey Shallit_, Sep 13 2016
%E A276691 a(20)-a(23) from _Robert Israel_, Sep 13 2016
%E A276691 a(24)-a(32) from _Joerg Arndt_, Sep 14 2016
%E A276691 a(33)-a(40) from _Joerg Arndt_, Sep 16 2016