A276691 Sum of maximum subrange sum over all length-n arrays of {1, -1}.

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

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 A340228

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