🐨BOJ# 11053]가장 긴 증가하는 부분 수열

import sys

def input():return sys.stdin.readline().rstrip()

def lis(arr):
    n = len(arr)
    dp = arr[:]  # 각 원소를 포함하는 부분 수열의 합의 초기값은 자기 자신으로 시작
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:  # arr[i]가 arr[j]보다 클 경우
                dp[i] = max(dp[i], dp[j] + arr[i])  # 최대 합을 업데이트
    return max(dp)

n = int(input())
a = list(map(int, input().split()))
print(lis(a))

import sys
input = sys.stdin.read
from bisect import bisect_left

def find_lis_length(sequence):
    if not sequence:
        return 0
    
    # LIS를 위한 최소 마지막 값들을 저장하는 배열
    lis_ends = []
    
    for value in sequence:
        # 현재 값이 lis_ends 배열의 어느 위치에 들어갈지 결정
        pos = bisect_left(lis_ends, value)
        
        # 만약 현재 값이 모든 마지막 값보다 크면 새로운 길이의 LIS 생성
        if pos == len(lis_ends):
            lis_ends.append(value)
        # 아니라면 기존 위치를 현재 값으로 업데이트 (더 작은 값으로)
        else:
            lis_ends[pos] = value
    
    # LIS의 최대 길이 반환
    return len(lis_ends)

# 입력 처리
data = input().split()
n = int(data[0])
sequence = list(map(int, data[1:]))

# LIS 길이 계산 및 출력
print(find_lis_length(sequence))

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