[Python] 백준 11053_ 가장 긴 증가하는 부분 수열

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.

1. DP정의

• dp: i번째까지 증가했을때 수열의 최대 길이
• d = [1]*n 으로 초기화 -> 최소 현재 부터 시작하는 길이 1인 수열이 존재 가능하므로

(예졔)
6
10 20 10 30 20 50

2. 점화식 찾기

d[i] = max(d[j]+1, d[i])
j = i앞의 index중 a[i]보다 a[j]가 작을 경우

3. 코드

import sys
input = sys.stdin.readline

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

#dp: i번째까지 증가했을떼 수열의 최대 길이 
d = [1]*n

for i in range(1,n):
    for j in range(i):
        if a[j]<a[i]:
            d[i] = max(d[j]+1,d[i])
print(max(d))

**처음에 구현한 틀린 코드
(반례)
6
10 20 10 30 20 50

import sys
input = sys.stdin.readline

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

#dp: i번째까지 더 했을 때 합 ?
d = [1]*n
now_n = a[0]

for i in range(1,n):
    if a[i]>now_n:
        d[i]=d[i-1]+1
        now_n = a[i]
    else:
        d[i]=d[i-1]
print(d[n-1])