https://www.acmicpc.net/problem/11055

D[i] : A[i]를 마지막으로 하는 증가 수열 중 가장 합이 큰 수열의 합

이라고 할 때

D[i] = max(D[j]+A[i]) for j = 0~i-1 s.t. satisfies A[j] < A[i] 입니다.

이렇게 하면 O(N^2)으로 풀 수 있습니다. 세그먼트 트리를 쓰면 O(NlgN)으로 풀 수 있습니다.

https://github.com/encrypted-def/BOJ/blob/master/11055.cpp