[BOJ] 11055번 - 가장 큰 증가 부분 수열

---

문제설명

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

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

사고과정

• LIS 알고리즘을 활용하는데, 문제에서 요구하는 것은 증가하는 부분 수열의 합이 가장 큰 것을 구하는 것이다. 무의식적으로 그냥 증가 부분 수열의 길이를 DP 테이블에 넣고 삽질하고 있었다..
• 문제에서 요구하는 것은 길이가 아닌 수열의 합이므로 DP 테이블에는 수열의 길이가 아닌 수열의 각 번째 자리에서 나올 수 있는 수열의 최대 합을 넣어주어야 한다..문제에서 요구하는 사항을 명확히 파악하는 연습을 더 해야할 듯 싶다..

풀이(스스로 못 푼 풀이)

n = int(input())
array = list(map(int, input().split()))
dp = [0] * n
dp[0] = array[0]

for i in range(1, n):
    res = []
    for j in range(0, i):
        if array[j] < array[i]:
            # 작은 수를 넣기
            res.append(dp[j])
    # res가 비어있으면
    if not res:
        dp[i] = array[i]
    else:
        dp[i] = array[i] + max(res)

print(max(dp))