

A276691


Sum of maximum subrange sum over all lengthn 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): 865873.
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^n1)'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



