[BOJ]11053. 가장 긴 증가하는 부분 수열

문제:

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

 

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A={10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

입력:

첫째 줄에 수열 A의 크기(1<=N<=1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1<=Ai<=1,000)

출력:

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이 방법:

배열을 하나씩 커지게 만들어 가면서 증가하는 부분 수열을 찾도록 한다. 가장 큰 값을 빠르게 찾기 위해서 뒤에서 부터 값을 탐색하도록 하게 한다.

N=int(input())
idx=[1]*N
A=list(map(int,input().split()))
 
for i in range(N):
    idx[i] = 1
    for j in range(i,-1,-1):
        if A[j] < A[i] and idx[j] >= idx[i]:
            idx[i] = idx[j] + 1
print(max(idx))

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