\(f_i: \mathbb{Z} \to \mathbb{R} \cup \{-\infty\}\) を、

\[ f_i(x) = \begin{cases} i \text{日目開始時点で} x \text{株保持している場合の利得の最大値} \quad & (x \geq 0) \\ -\infty \quad & (x \lt 0) \end{cases} \]

と定義します。\(\displaystyle \max_x f_N(x)\) が求める答えです。

\(f_{i+1}\) を \(f_i\) から計算することを考えましょう。 やっていることは動的計画法と全く同様なので、

\[ f_{i+1}(x) = \begin{cases} \displaystyle \max _ {-1 \leq s \leq 1} f_i(x-s) - P_i s \quad &(x \geq 0) \\ - \infty \quad &(x \lt 0) \end{cases} \]

となります。 ここから、\(f_i\) は凹関数になることが分かります。 なぜなら、

\[ g_i(x) = \begin{cases} -P_i x \quad &(-1 \leq x \leq 1) \\ -\infty \quad &(\text{otherwise}) \end{cases} \\ h(x) = \begin{cases} 0 \quad &(x \geq 0) \\ -\infty \quad &(x \lt 0) \end{cases} \]

と定義すれば

\[ f_{i+1} = f_i \diamond g_i + h \]

と表現できるからです。 ここで、\(2\) つの凹関数 \(f_1, f_2\) の supremal convolution \(f_1 \diamond f_2\) は

\[ (f_1 \diamond f_2)(x) = \sup_{s + t = x} (f_1(s) + f_2(t)) \]

によって定義され、再び凹関数になります。

以上より、凹関数の和と supremal convolution を高速に計算することができればこの問題を解くことができます。 平衡二分探索木を用いたアルゴリズムなどが知られていますが、今回は \(g_i\) や \(h\) が単純な形をしているため、整理することで公式解説と同様のアルゴリズムを導出することも可能です。