\(M\) の制約がない場合，以下のようにして問題を解くことができます．

• 各 \(1 \leq i \leq N\) について，\(A\) の後ろ \(i\) 項の和を \(sum(i)\) とする．そして，\(sum(i)/i\) を最大化する \(i\) を \(m\) とおく．そして，\(x\) の最初の \(N-m\) 項を \(0\)，最後の \(m\) 項を \(S/m\) にする．

これは次のように証明できます． 今，ある最適解 \(x\) があり，\(i \neq N-m\) 以外で \(x_i < x_{i+1}\) (\(0 \leq i \leq N-1\)) であったとします． なお，便宜的に \(x_0=0\) であるとし，\(i=0\) も考慮に入れることにします． ここで，\(d=x_{i+1}-x_i\) とおきます．\(x\) の後ろ \(N-i\) 項から \(d\) を引き，その後 \(x\) の後ろ \(m\) 項に \(d \times (N-i)/m\) を足すことで，\(x\) の総和を保ち，スコアを減らさず，\(x_i < x_{i+1}\) を満たす \(i\) の個数を減らすことができます． この操作を繰り返すと，先に述べたような，後ろ \(m\) 項が \(S/m\) であるような \(x\) が得られます．

\(M\) の制約を考えてみます． 上記と同様の議論で，以下のことがわかります．

• \(S/m \leq M\) のとき，後ろ \(m\) 項を \(S/m\) にする解が最適．
• \(S/m > M\) のとき，最適解では後ろ \(m\) 項は \(M\) であるとしてよい．

前者のケースのスコアは明らかです． 後者のケースでは，単に \(N-m\) 項の \(A\) に対する問題を続けて解くことで最適解がわかります．

上の手順を素直に実装すると，\(O(N^2)\) 時間のアルゴリズムが得られ，これは十分高速です．

おまけ：上記のアルゴリズムをよく観察することで，この問題は \(O(N)\) で解くことができます．（ヒント：凸包）