(파이썬 python) 백준 11055번 : 가장 긴 증가 부분 수열

n = int(input())

li = list(map(int,input().split()))

#증가하는 수열 - LIS
dp = li[:]
for i in range(n):
    for j in range(i):
        if li[i] > li[j]:
            dp[i] = max(dp[i],dp[j]+li[i])

print(max(dp))

11054번에서 만든 증가하는 부분수열 구하는 알고리즘에서 부분수열의 개수를 구하는 것이 아니라 부분수열의 합을 구해서 dp리스트에 업데이트를 해주면 된다. 

 

아래 코드는 증가하는 부분수열의 개수를 구하는 알고리즘이다. 비교를 해보면 위의 dp[j]+li[i]는 부분수열의 합을 구하기 위한 계산이고 dp[j]+1은 부분수열의 개수를 구하기 위한 계산이다.

 

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

#증가하는 수열 - LIS
dp= [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if li[i] > li[j]:
            dp[i] = max(dp[i],dp[j]+1)