====== 가장 큰 증가 부분 수열 ======

===== 풀이 =====
  * [[ps:가장 긴 증가하는 부분 수열]]을 살짝 변형시킨 문제.
  * 그냥 DP나 세그먼트 트리 방법으로 풀때는 [[ps:가장 긴 증가하는 부분 수열]]을 풀때와 거의 유사하게 풀 수 있다. 
  * 하지만, 이분탐색으로 [[ps:가장 긴 증가하는 부분 수열]]을 풀때 썼던 알고리즘은 적용하기가 어렵다. 살짝 변형해서 적용할수 있는 방법을 한참 고민했지만 불가능한것으로 결론내림..
  * 그냥 DP로 풀면 O(n^2), 세그먼트 트리로는 O(nlogm)이지만, 문제에서 n이 작게 주어지다보니, 실제 수행시간은 상수가 작은 DP쪽이 더 빨랐다

===== 코드 =====

==== DP (O(n^2))====
<dkpr py>
"""Solution code for "BOJ 11055. 가장 큰 증가 부분 수열".

- Problem link: https://www.acmicpc.net/problem/11055
- Solution link: http://www.teferi.net/ps/problems/boj/11055

Tags: [LIS] [DP]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    dp = []
    for a_i in A:
        prev_max = max((dp_j for dp_j, a_j in zip(dp, A) if a_j < a_i),
                       default=0)
        dp.append(a_i + prev_max)

    print(max(dp))


if __name__ == '__main__':
    main()
</dkpr>

==== Segment Tree (O(nlogm))====
<dkpr py>
"""Solution code for "BOJ 11055. 가장 큰 증가 부분 수열".

- Problem link: https://www.acmicpc.net/problem/11055
- Solution link: http://www.teferi.net/ps/problems/boj/11055

Tags: [LIS] [Segment Tree]
"""

from teflib import segmenttree


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    size = max(A) + 1
    segtree = segmenttree.SegmentTree([0] * size, merge=max)
    for a_i in A:
        prev_max = segtree.query(0, a_i)
        segtree.set(a_i, prev_max + a_i)

    print(segtree.query(0, size))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:segmenttree#SegmentTree|teflib.segmenttree.SegmentTree]]

{{tag>BOJ ps:problems:boj:실버_2}}