Part7.4_2_동적프로그래밍(DynamicProgramming)_최대부분 증가수열(LIS:Longest Increasing Subsequence)

문제

수열이 주어지면 오름차순을 가장 길어지는 최대 부분 증가수열을 구해라.
ex) 2, 7, 5, 8, 6, 4, 7 의 경우에는
ans) 2, 5, 6, 7, 12 가 가장 긴 증가수열이다.

입력

첫째 줄에는 데이터의 수 N(2<=N<=1000)
둘째 줄에는 N개의 입력 데이터가 주어진다.

출력

첫번째 줄에 부분 증가수열의 최대 길이를 출력한다.

풀이

arr 에 수열을 초기화하고, for문을 2부터 돌면서~N까지 i 가 마지막이라고 생각하고 이중 for문으로 1부터 i까지 증가수열을 찾는다

코드

import sys

sys.stdin=open("input.txt","rt")

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

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int,input().split()))
    arr.insert(0,0)
    
    res = [0]*(n+1)
    res[1] = 1
    len = 0
    print(res)
    for i in range(2,n+1):
        max = 0  
        for j in range(i-1,0,-1):
            if arr[i]>arr[j] and res[j]>max:
                max = res[j]
        res[i] = max+1 # 여기서 무조건 +1이 count 된다
        print(res)
        if res[i] > len:
            len = res[i]
    print(res)