|
|
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
|
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|