[BOJ] 11055 / 가장 큰 증가 부분 수열 / Python

[BOJ] 11055 / 가장 큰 증가 부분 수열 / Python

[BOJ] 11055 / 가장 큰 증가 부분 수열 / Python

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

11055번: 가장 큰 증가 부분 수열

풀이

[BOJ] 11053 / 가장 긴 증가하는 부분 수열 의 연관 문제이다.

 

수열의 길이가 아닌 LIS 부분 수열의 원소 합을 구해야 한다.

N = int(input())

nums = list(map(int, input().split()))
dp = [1] * N

for i in range(N):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[i], dp[j]+1)
        
print(max(dp))

 

부문 문제 해결의 결과로 전체 문제를 해결하는 생각이 중요하다.