各 \(i\) について，\(A_i\) の前に来る符号が + である場合の数と - である場合の数を求める DP をすればよいです．

\(dp[i][j]=i\) 個 +- を並べて，- が連続しないようにして，最後が + (\(j=0\) のとき) または - (\(j=1\) のとき) であるような場合の数　とすればよいです．

各 \(2 \leq i \leq N\) について，\(A_i\) の前に来る符号を決めたとすると，先頭 \(i-2\) 個の符号の決め方と後ろ \(N-i\) 個の符号の決め方は独立になり，またそれは上記の \(dp\) の値から計算できます．

計算量は \(O(N)\) です．