[백준] 11055번 문제 (가장 큰 증가 부분 수열) 파이썬(Python) 풀이

n = int(input())
nums = list(map(int, input().split()))
dp = nums[:]

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

 

 

https://honggom.tistory.com/80

[백준] 11053번 문제 (가장 긴 증가하는 부분 수열) 파이썬(Python) 풀이

백준에는 '가장 ... 수열' 이라는 이름으로 유사한 dp 문제가 여럿있다. 

이 문제도 그 중에 하나로 앞서서 작성한(위 링크)문제와 매우 유사한 문제다. 

 

for문이 이중으로 있는데,

바깥 for문은 0 ~ n - 1까지 반복되고,

안쪽 for문은 0 ~ 바깥 for문의 인덱스 - 1까지 반복된다.

 

그러면서 nums[i] > nums[j] 가 성립되면 dp[i]에 nums[i] + dp[j]을 할당하며 수열의 크기를 점진적으로 더하며 구한다.