次のような DP を考えます．

\(dp[i][j]=\) 最初の \(i\) 項に操作を行った結果であって，\(A_i\) の値が \(A_i+j\) に変化するようなものの個数 (\(j \neq 0\))

\(j \neq 0\) の制約により，\(dp[i][j]\) で数えている操作では必ず \(A_i\) を選んで操作しているとわかります． つまり，この次に選ぶ項は \(A_i+j\) だけ増加することになります．

\(A_i+j \neq 0\) の場合の遷移は簡単です． \(A_i+j=0\) の場合はどうなるでしょうか？

次に変化する項を \(A_k\) とします．\(A_k \to A_k+v\) と変化するためには，\(A_{i+1},\cdots,A_{k-1}\) の中から \(v\) となる値を選べばよいです．

可能な遷移は上に上げたもので全てです． これらを適切に実装すれば \(O(N^3 \max(|A_i|))\) 時間でこの問題は解けます．

回答例(C++)