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

 

Logo


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 January 19 06:39 EST 2018. Contains 297896 sequences.