login
This site is supported by donations to The OEIS Foundation.

 

Logo

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

Table of n, a(n) for n=1..40.

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 18:46 EST 2017. Contains 294894 sequences.