E - Doubling

dpをします。

• $dp[l][r]=$ 区間 $[l,r]$ でこの問題を解いた時の解

とします。
この値は、 $l<i<r$ に対して以下の値を計算した時の最大値です。

• $2×\rm{max}$ $(dp[l][i-1],dp[i+1][r])+\rm{min}$ $(dp[l][i-1],dp[i+1][r])+\rm{max}$ $(A_{i-1},A_{i+1})$ $\rm{mod}$ $\rm{min}$ $(A_{i-1},A_{i+1})$

計算量は $O(N^3)$ です。