This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.