Efficient algorithm for existence of permutation with differences sequence?
This is a sketch of a possible reduction to prove that it is NP-hard:

1) $a_i$ subsequences made of 1s (e.g. $...11111...$) (I call them 1SEQ) force a subsequence of increasing or decreasing numbers in the permutation;

2) if a value of $2$ is put in a long 1SEQ,  it forces a hole (a missing number) and doesn't change the direction of the 1SEQ. For example: $1112112111$ forces two holes:

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)


The holes must be filled in the rest of the permutation.

3) using a large enough 1SEQ, followed by a 1SEQ with some holes, followed by another large 1SEQ you can build a forced line;

4) putting together many forced lines you can build a permutation grid graph in which the nodes correspond to the missing numbers in the underlying forced permutation.

For example the sequence 1111111112111111111112111111111, forces the following 5x7 permutation grid graph:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14   
 1  2  3  4  5  6  7


(or its symmetric version). Note that if the grid has size $w \times w$ and $a,b$ are two missing numbers in the same vertical column then $|a-b|=kw$.

5) the Hamiltonian cycle on grid graphs problem is NP-complete; so given a grid graph $G$ (with holes) you can build the equivalent permutation grid graph;

6) from the last number of the permutation you can "jump" to a number corresponding to a hole (a node in $G$), and with a fixed sequence of moves you can simulate the traversal of $G$; this requires a rather complex gadget - the "selection gadget" - that must be created in another part of the permutation grid graph;

7) you can fill all the holes (i.e. complete the permutation) if and only if the original grid graph has an Hamiltonian cycle

EDIT: July, 27 2013

I tried to formally prove the NP completeness of the problem: I introduced a new problem (Crazy Frog problem) which is NPC.
The Permutation Reconstruction from Differences problem is equivalent to the "1-D Crazy Frog problem without blocked cells" (which is also NPC).

For the details of the reduction see my question/answer  on cstheory
"Two Hamiltonian path variants" or download a draft of the proof "When a frog meets a permutation" :)) (I'm still checking/completing it)