[백준/Python] 11055번: 가장 큰 증가하는 부분 수열

문제

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

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

---

문제 요약

수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 가장 큰 합을 출력한다.

 

예를 들어 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우,

가장 큰 증가하는 부분 수열은 {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}이므로 답은 113이다.

---

코드

N = int(input())

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

dp = A[:]
# dp[i]는 i번째 인덱스까지 i번째 인덱스를 포함한 증가하는 부분 수열의 합 중 가장 큰 값.
# 초기 값 dp[i]는 A[i]

for i in range(N):
    for j in range(i): # A[j]는 A[i] 왼쪽에 있는 값들을 하나씩 접근
        if A[j] < A[i] and dp[i] < dp[j] + A[i]:
        # A[i]가 A[j]보다 크고, 
        # j인덱스까지 가장 큰 값에 A[i]를 더한 값이 이전까지 있었던 가장 큰 값보다 크다면,
            dp[i] = dp[j] + A[i]

print(max(dp))

---

코드 설명

1. 메모이제이션 테이블 dp를 설정한다.

+ dp[i]는 i번째 인덱스까지 i번째 인덱스를 포함한 증가하는 부분 수열의 합 중 가장 큰 값이다.

+ 초기 값을 A[i]로 저장한 이유는 i번째 인덱스까지 증가하는 부분 수열이 없을 때, 자기 자신만 존재하는 수열이 증가하는 부분 수열 중 가장 큰 값을 갖는 수열이기 때문이다.

 

2. 이중 반복문을 통해 A[i] 이전에 존재하는 값들(A[j])을 모두 접근한다.

 

3. A[j]보다 A[i]가 더 크고 (증가하는 수열), j 인덱스까지 가장 큰 값에 A[i]를 더한 값이 이전까지 있었던 가장 큰 값보다 크다면 (가장 큰 합), dp[i]를 갱신한다. 

 

4. dp 배열 중 가장 큰 값을 출력한다.