\(\Leftarrow\) は明らかです。\(\Rightarrow\) を証明します。

\(S= t_1 + t_2 + ... + t_k(k \ge 3)\) と分割出来たとします。このとき、\((t_1,t_2+t_3+\dots + t_k)\) という長さ \(2\) の分割は条件を満たします。辞書順で \(t_1 < t_2\) かつ \(t_2 < t_2 + t_3 + \dots + t_k\) であることより、\(t_1 < t_2 + t_3 + \dots + t_k\) が成り立つためこの分割は vaild です。

よって、\(S\) を長さ \(2\) に分割する方法であって辞書順で狭義単調増加なものがあるかを全て確認すればよいです。そのような分割方法は \(N-1\) 個あり、それぞれの判定に \(\mathrm{O}(N)\) かけることで \(\mathrm{O}(N^2)\) でこの問題を解くことが出来ます。