Let’s consider the following DP:

\(dp[i][j]=\) The number of ways to perform the operation on the first \(i\) terms so that the value of \(A_i\) changes to \(A_i+j\) (\(j \neq 0\)).

Due to the constraint \(j \neq 0\), we know that the operation counted in \(dp[i][j]\) always selects \(A_i\) for the operation. That is, the next term to be selected will increase by \(A_i+j\).

The transition for the case \(A_i+j \neq 0\) is simple. What happens when \(A_i+j=0\)?

Let \(A_k\) be the next term to be changed. To change \(A_k \to A_k+v\), we need to select the value \(v\) from \(A_{i+1},\cdots,A_{k-1}\).

The above covers all possible transitions. By implementing these appropriately, this problem can be solved in \(O(N^3 \max(|A_i|))\) time.

Sample Solution (C++)