求最大和上升子序列的 $O(n)$ 或 $O(n \log n)$ 做法

蒟蒻只会 $O(n^2)$ 的 $DP$

$P.S.$ 即 $\max_{\substack{1\le i_1<i_2..<i_k\le n\\ a_{i_1}<a_{i_2}..<a_{i_k}}}\sum_{j=1..k}a_{i_j} (1 \le n \le 10^5,1\le a_i\le 10^9)$