Consider an array $A$ of length $n$ with $A\_i \in \{1,\dots,s\}$ for some $s\geq 1$. For example take $s = 6$, $n = 5$ and $A = (2, 5, 6, 3, 1)$. Let us define $g(A)$ as the collection of sums of all the non-empty contiguously indexed subarrays of A. In this case 
$$g(A) = [2,5,6,3,1,7,11,9,4,13,14,10,16,15,17]$$


In this case all the sums are distinct. However, if we looked at $g((1,2,3,4))$ then the value $3$ occurs twice as a sum and so the sums are not all distinct.


For $s \geq 1$, I would like to understand what the largest $n$ is such that that there exists an array $A$ of length $n$ with all distinct $g(A)$. This question arose orginally as a [coding competition](https://codegolf.stackexchange.com/questions/175548/find-arrays-with-distinct-subarray-sums) and the answers for $s = 1,\dots, 21$ are $n = 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 11, 11, 12, 13, 13, 14, 14$.



> 
> On the assumption that an exact formula is hard to come by, is it
>  possible to show its asymptotics? For example, is it true that
>  $n$ is $\Theta(s)$?
> 
> 
> 



Bounds for the size of arrays with distinct subarray sums
Let $0=:x\_0<x\_1<x\_2<\dots<x\_n$ be the sums of initial segments of $A$. Then your condition is that the mutual differences of $x$'s are pairwise distinct, in other words, $X=\{x\_0,x\_1,\dots,x\_n\}$ is a [Sidon set](https://en.wikipedia.org/wiki/Sidon_sequence). Additional requirement is that consecutive elements of $X$ differ at most by $s$. This of course means that $n\leqslant s$ and I claim that $n=(1/3+o(1))s$ is possible. 


For this we may use one of standard constructions of Sidon set. Let $p>2$ be a prime number and consider the set of numbers $x\_k=2pk+\{k^2\}\_p$, where $\{x\}\_p$ denotes a remainder of $x$ modulo $p$ and $k$ varies from 0 to $p-1$. Obviously $x\_{k+1}-x\_k<3p$ for all $k=0,1,\dots,p-1$ and the equation $x\_i+x\_j=x\_u+x\_v$ implies $i+j=u+v$, $\{i^2\}\_p+\{j^2\}\_p=\{u^2\}\_p+\{v^2\}\_p$ (considering remainders and quotients of both parts modulo $2p$), thus modulo $p$ we have $i+j=u+v$, $i^2+j^2=u^2+v^2$, $(i-u)(i+u)=(v-j)(v+j)$, $(i-u)(i+u-v-j)=0$, either $i=u,v=j$ or $i+u=v+j=v+u+v-i$, $i=v,u=j$. Therefore this is indeed a Sidon sequence and for any $s\geqslant 3p-1$ we get an array of length $p-1$. Since the primes number are frequent enough, this yields that $n=(1/3+o(1))s$ is possible.


The upper bound $n\leqslant s$ also may be improved using the [idea](https://users.renyi.hu/~p_erdos/1941-01.pdf) of Erdos and Turan on Sidon sets. Namely, we may consider the differences $x\_j-x\_i$ for $0<j-i\leqslant t$ ($t$ is large but $t=o(n)$). There are $tn+o(tn)$ such differences, and their sum does not exceed $\frac{t(t+1)}2x\_n\leqslant \frac{t(t+1)}2 (s+(s-1)+\dots+(s-n))$. Thus we get $\frac12t^2n(s-n/2)\geqslant \frac{(tn)^2}2 (1+o(1))$, $n\leqslant \frac23s+o(s)$. 


Your sequence suggests that this upper bound is less or more tight.


