買って売らない株があるのは無駄なので，この問題は買いと売りのマッチング問題と見なせます． 売値が買値以下であるような取引は得をしないことから，具体的には，$2$ 次元平面上の格子点 $(1, P_1), (2, P_2), \dots, (N, P_N)$ を頂点とし，$i < j$ かつ $P_i < P_j$ であるような頂点対 $(i, P_i), (j, P_j)$ 間に重み $P_j - P_i$ の辺を張ったグラフにおける最大重みマッチング問題となります． 陽にグラフを構成すると辺の数が最悪 $\binom{N}{2} = \Theta(N^2)$ になってしまって多すぎますが，今回の設定では以下のような貪欲法でこの問題を解くことができます． （参考：重み無しかつ $2$ 部グラフかつ制約が小さい問題 ABC091-C 2D Plane 2N Points ）

$k = 0, 1, \dots, N$ に対し，頂点を $(1, P_1), (2, P_2), \dots, (k, P_k)$ に制限した場合の最適解を順に求めます． $k \le 1$ の場合は空集合のみがあり得るマッチングなので，明らかにこれが最適解です． 最大重みマッチングに関する一般論として，$k - 1$ の場合の最適解 $M_{k-1}$ が $k$ の場合の最適解でない場合には，$(k, P_k)$ を端点とする交互道（マッチ辺と非マッチ辺を交互に通るパス）に沿って $M_{k-1}$ からマッチ／非マッチ辺を交換して得られるようなマッチングであって，$k$ の場合の最適解であるようなものが必ず存在します．（そうでなければ，$(k, P_k)$ を使わずに $M_{k-1}$ を真に改善できるような交互道 or 交互閉路が存在し，$M_{k-1}$ の最適性に矛盾します．） 特に今回の場合は，以下（折りたたみ）に示すように，長さ $2$ 以下の交互道に沿った交換，すなわち，

• 単純に $(k, P_k)$ を非マッチ頂点とマッチさせる
• マッチ辺 $\{(i, P_i), (j, P_j)\} \in M_{k-1}$ を取り除いて新たに $(i, P_i), (j, P_j)$ のいずれか一方を $(k, P_k)$ とマッチさせる

という交換のみを考えれば十分です．

証明

$M_{k-1}$ から $k$ の場合の最適解を得るために長さ $3$ 以上の交互道 $Q$ に沿った交換が必要だったとして，この $Q$ を交換後の重みの意味で損しないように短縮できることを示します．

$Q$ の先頭 $2$ 辺を順に $\{(k, P_k), (j, P_j)\}, \{(j, P_j), (i, P_i)\}$ としましょう． $i < j~~(\Leftrightarrow~P_i < P_j)$ であれば，$Q$ 全体を $\{(k, P_k), (i, P_i)\}, \{(i, P_i), (j, P_j)\}$ の $2$ 辺で置き換えて損をしません． なぜなら，$Q$ の $(j, P_j)$ 以降の部分は $k - 1$ の時点でも交換可能で，その交換で得しない（元の $M_{k-1}$ が最適解である）はずなので，$Q$ に沿った交換による重みの増加量は高々 $P_k - P_j$ であり，置き換え後の交互道に沿った交換による重みの増加量は $(P_k - P_i) - (P_j - P_i) = P_k - P_j$ となるからです． よって $j < i~~(\Leftrightarrow~P_j < P_i)$ を仮定してよいです．

$Q$ の $3$ 辺目を $\{(i, P_i), (h, P_h)\}$ とします． $h < i~~(\Leftrightarrow P_h < P_i)$ のとき，

• $P_h < P_k$ であれば，$Q$ の先頭 $3$ 辺を $\{(k, P_k), (h, P_h)\}$ の $1$ 辺で置き換えることができ，このとき交換による重みの増加量は変化しません．（ $Q$ の対応する部分での増加量が $(P_k - P_j) - (P_i - P_j) + (P_i - P_h) = P_k - P_h$ であり，これは置き換え後と同じ値です．）
• $P_h \ge P_k$ であれば，$Q$ の $(h, P_h)$ 以降の部分は $k - 1$ の時点でも交換可能で得をしないはずので，$Q$ に沿った交換による重みの増加量が高々 $(P_k - P_j) - (P_i - P_j) + (P_i - P_h) = P_k - P_h \le 0$ となり，$Q$ に沿った交換で $M_{k-1}$ より良いマッチングが得られるという前提に矛盾します．

$i < h~~(\Leftrightarrow P_i < P_h)$ のとき，$Q$ の先頭 $3$ 辺を $\{(i, P_i), (j, P_j)\}, \{(j, P_j), (h, P_h)\}$ の $2$ 辺で置き換えて得られる交互道 $Q'$ を考えます． これは $j < i < h$ かつ $P_j < P_i < P_h$ なので可能です． すると，$Q$ と $Q'$ に沿った交換による重みの増加量の差分は先頭部分だけで決まり，その値は $\bigl((P_k - P_j) - (P_i - P_j) + (P_h - P_i)\bigr) - \bigl(-(P_i - P_j) + (P_h - P_j)\bigr) = P_k - P_i$ となります． $Q'$ は $k - 1$ の時点でも交換可能で得をしないはずなので，$Q$ に沿った交換による重みの増加量は高々 $P_k - P_i$ です． ここで，$Q$ 自体を先頭 $2$ 辺で打ち切って得られる交互道を考えると，これは交換可能かつ重みの増加量が $(P_k - P_j) - (P_i - P_j) = P_k - P_i$ となって損をしないことがわかります．

以上より，各更新ステップでは，長さ $2$ 以下の交互道に沿った交換を考えれば十分であることが示せました． そのようなもののうち交換後の重みが最大になるものが見つかればよいので，優先度付きキューを用いて

• 非マッチ頂点 $(i, P_i)$ with key $P_i$
• マッチ辺の大きい方の端点 $(j, P_j)$ with key $P_j$

を（どちらのパターンであるかの情報とともに）管理し，最小 key と追加された頂点 $(k, P_k)$ の値 $P_k$ を比較して，マッチングを更新するかどうかを決めればよいです． 前者との更新では $(k, P_k)$ with key $P_k$ が後者のパターンで追加され，後者との更新ではそれに加えて $(j, P_j)$ with key $P_j$ が前者のパターンで追加されます． また，更新が起こらない場合には $(k, P_k)$ with key $P_k$ が前者のパターンで追加されます．

実装例 (C, 50 ms)