転倒数が最大となる長さ \(N\) の順列は \((N,N-1,...,2,1)\) です。

ここで、\(N\) の偶奇で場合分けをします。

• \(N\) が偶数の場合
上記の順列が攪乱順列であるため、\((N,N-1,...,2,1)\) が最適解となります。よって解は \(\displaystyle \frac{N(N-1)}{2}\) です。
• \(N\) が奇数の場合
\(\displaystyle \frac{N+1}{2}\) 番目の項が \(\displaystyle \frac{N+1}{2}\) であるため、\((N,N-1,...,2,1)\) は攪乱順列ではありません。また、\(\displaystyle \frac{N+1}{2}\) 番目と \(\displaystyle \frac{N+1}{2}+1\) 番目の項を入れ替えた場合、転倒数を \(1\) 減らし攪乱順列を構成することができます。\((N,N-1,...,2,1)\) 以外に転倒数が \(\displaystyle \frac{N(N-1)}{2}\) 以上である順列は存在しないため、解は \(\displaystyle \frac{N(N-1)}{2}-1\) です。

以上より本問題を \(\mathrm{O}(1)\) で解くことができます。