By partial summation
$$ s(n) = n\pi(n)-\sum_{m=2}^{n-1}\pi(m) $$
so by the Prime Number Theorem
$$ s(n) = \frac{n^2}{\log n}-\sum_{m=2}^{n-1}\frac{m}{\log m}+O\left(\frac{n^2}{\log^2 n}\right). $$
The sum on the right is
$$ \sum_{m=2}^{n-1}\frac{m}{\log m} = \int_2^n \frac{x}{\log x}dx + O\left(\frac{n}{\log n}\right) $$
using the monotonicity properties of the integrand. Now the integral equals, by partial integration,
$$ \int_2^n \frac{x}{\log x}dx = \left[\frac{x^2}{2\log x}\right]_2^n + \int_2^n \frac{x}{2\log^2 x}dx = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$
Altogether we have
$$ s(n) = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$
This can be made more precise both numerically and theoretically.
The problem can be solved as follows using dynamic programming. Suppose the sequence is
x_1, ..., x_n
and we wish to determine if there is a nonempty subset which sums to s. Let N be the sum of the negative values and P the sum of the positive values. Define the boolean-valued function Q(i,s) to be the value (true or false) of
"there is a nonempty subset of x_1, ..., x_i which sums to s".
Thus, the solution to the problem is the value of Q(n,0).
Clearly, Q(i,s) = false if s < N or s > P so these values do not need to be stored or computed. Create an array to hold the values Q(i,s) for 1 ≤ i ≤ n and N ≤ s ≤ P.
The array can now be filled in using a simple recursion. Initially, for N ≤ s ≤ P, set
Q(1,s) := (x_1 == s).
Then, for i = 2, …, n, set
Q(i,s) := Q(i − 1,s) or (x_i == s) or Q(i − 1,s − x_i) for N ≤ s ≤ P.
For each assignment, the values of Q on the right side are already known, either because they were stored in the table for the previous value of i or because Q(i − 1,s − xi) = false if s − x_i < N or s − x_i > P. Therefore, the total number of arithmetic operations is O(n(P − N)). For example, if all the values are O(n^k) for some k, then the time required is O(n)^k+2
Best Answer
In the modern language, sets with all subset sums pairwise distinct are often called dissociated. Maximal dissociated subsets of a given set are important in Additive Combinatorics and Fourier analysis, although I cannot recall anybody ever addressing the algorithmic aspect.
Yet another reference you may find useful: http://math.haifa.ac.il/~seva/Papers/DisBases.pdf.
Added: taking into account the interpretation of a maximal dissociated subset of a given set $A$ as a "basis of $A$ over the set $\{-1,0,1\}$", it may be reasonable to try and adjust one of the standard algorithms of finding a maximal independent subset of a given set in a vector space.