[이코테][Python][DP] LIS

n = int(input())

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

for i in range(1, n):  
  for j in range(0, i):
    if arr[j] < arr[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

 

0 <= j < i 인 모든 j에 대해 arr[j]가 arr[i]보다 작다면 기존의 dp[i]와 dp[j]+1을 비교하여 큰 값을 갱신해준다.

이런식으로 n-1번 반복하면 주어진 배열에 대해 가장 긴 증가하는 부분 수열을 구할 수 있다.

4 2 5 8 4 11 15에서 4 5 8 11 15를 구할 수 있는데,

5는 2가 5보다 작으니 dp[1]+1과 기존 dp[2]인 1을 비교하여 더 큰 수인 2가 dp[2]에 갱신됨.

8은 5가 8보다 작으니 dp[2]+1과 기존 dp[3]인 1을 비교하여 더 큰 수인 3이 dp[3]에 갱신됨.

4는 2가 4보다 작으니 dp[1]+1과 기존 dp[4]인 1을 비교하여 더 큰 수인 2가 dp[4]에 갱신됨.

.

.

.

이러면 dp[n]이 5로 갱신되면서 max(dp)는 5가 됨.