The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A276691 Sum of maximum subrange sum over all length-n arrays of {1, -1}. 2
 1, 4, 11, 27, 63, 142, 314, 684, 1474, 3150, 6685, 14110, 29640, 62022, 129337, 268930, 557752, 1154164, 2383587, 4913835, 10113983, 20787252, 42668775, 87479539, 179157497, 366547820, 749256450, 1530251194, 3122882776, 6368433118, 12978230568, 26431617730, 53799078716, 109442256914, 222519713892, 452208698216, 918560947022, 1865036287632, 3785181059505, 7679199158098 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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. 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. LINKS Joerg Arndt, C++ program for this sequence, (2016) Jon Bentley, Programming pearls: algorithm design techniques, Communications of the ACM, (1984) 27 (9): 865-873. discussion on Quora (not all comments there are correct) EXAMPLE 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. Thus the sum is 3+(2*2)+4*1 = 11. PROG (MATLAB) for n = 1:23   L = 2*(dec2bin(0:2^n-1)-'0')-1;   S = L * triu(ones(n, n+1), 1);   R = max(S, [], 2);   for i = 1:n     R = max(R, max(S(:, i+1:n+1), [], 2) - S(:, i));   end   A(n) = sum(R); end A  % Robert Israel, Sep 13 2016 CROSSREFS Cf. A272604. Sequence in context: A034345 A036890 A000253 * A047859 A100335 A080869 Adjacent sequences:  A276688 A276689 A276690 * A276692 A276693 A276694 KEYWORD nonn AUTHOR Jeffrey Shallit, Sep 13 2016 EXTENSIONS a(20)-a(23) from Robert Israel, Sep 13 2016 a(24)-a(32) from Joerg Arndt, Sep 14 2016 a(33)-a(40) from Joerg Arndt, Sep 16 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 22 09:22 EST 2020. Contains 332133 sequences. (Running on oeis4.)