[python] 백준 11055 - 가장 큰 증가하는 부분 수열

출처 : 백준, https://www.acmicpc.net/problem/11055

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

 

 

수열 시리즈....

 

 

먼저, 생각해야 할 부분

 

1. 습관적으로 dp 배열을 0으로 초기화했는데 과연 0으로 초기화하는게 맞는지 생각해보자.

 

---

 

풀이

 

def solution(n, num_list):
    dp = num_list[:]

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

    return max(dp)

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

print(solution(n, num_list))

 

---

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들