[백준] 11055 가장 큰 증가 부분 수열 (Python)

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

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 1 복사

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1 복사

113

---

문제 풀이

 

입력되는 수열의 크기가 1000 이하로 작으므로, O(N^2)도 가능하다는 사실을 알 수 있다.

 

증가되는 수열인지를 알기 위해서는 현재의 수까지 증가하는 수열의 합을 저장하면 된다.

배열 초기화는 수열의 원소들로 초기화

 1) 앞서고 있는 수열을 확인하여 해당 수열의 크기가 작으면

 2) 해당 증가 수열과 현재 값을 더하여 현재 배열의 크기와 비교 후 대치한다.

---

코드

 

# 증가 부분 수열 중 합이 가장 큰 것.

N = int(input())
A = list(map(int ,input().split()))
dp = [i for i in A]
for i in range(1,N):
    for j in range(i):
        if A[j] < A[i]:
            if dp[i] < dp[j] + A[i]:
                dp[i] = dp[j] + A[i]
print(max(dp))

---