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

🔦 문제 링크

✍️ 나의 풀이

---

가장 길게 증가하는 부분수열이므로
기본적으로 첫 숫자부터 현재 인덱스까지 증가하는 갯수를 구하면 된다.
하지만 일부만 보는 것이 아니라 전체 숫자를 모두 봐야한다.
현재 검사하는 수(a[i])보다 작은 값만 인정되기 때문이다.
너무 큰 숫자가 앞에 나와버리면 가장 긴 증가부분수열이 될 수 없다.
따라서, 모든 값에 대해 for문을 반복해줘야 한다.

🛠 나의 코드

---

n = int(input())
a = [0] + list(map(int, input().split()))
dp = [0]*(n+1)

mx = -1
for i in range(1, n+1):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
    mx = max(mx, dp[i]) # => 이 부분이 꼭 필요하다.
    # 왜냐하면 꼭 마지막 원소가 최대길이를 가지지 않는다. 따라서 원소중 최대길이를 구해야한다.
print(mx)

📝 정리

---

🎈 참고

---