Bounds for the size of arrays with distinct subarray sums 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 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)$?

 A: 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. 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 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.
