[Python] Baekjoon - 11055. 가장 큰 증가 부분 수열

백준 11055번 가장 큰 증가 부분 수열은 수열의 증가 부분 수열 중 원소들의 합의 최댓값을 구하는 문제다. 다이나믹 프로그래밍 기법을 통해 해결할 수 있으며 난이도는 실버 2이다.

 

백준 11055번 가장 큰 증가 부분 수열 문제 정보

알고리즘 분류

• 다이나믹 프로그래밍

난이도

• 실버 2

 

가장 큰 증가 부분 수열 문제 요약

• 수열의 증가 부분 수열 중 원소들의 합의 최댓값 구하기
• 부분 증가수열은 [1,1,3,2,4]에서 [1,3,4]처럼 원소가 증가하는 부분 수열(같은 원소 X)

 

문제 풀이 방법

과정

• 증가 부분 수열이 크거나 '같으면'되는 줄 알고 풀었다가 계속 틀려서 한참 헤맸다..
• 다이나믹 프로그래밍을 이용해서, i번째 수를 포함하는 증가 부분 수열 중 원소 합의 최댓값을 저장하는 배열 S를 만들어 사용한다.

풀이

• S [i] 구하기

1. i > j인 j 중 S[j]가 가장 큰 j를 구한다.
2. S[i] = S[j] + (i번째 원소) (j 없으면 S[i] = (i번째 원소))
3. S[i] 중 가장 큰 값을 반환

 

코드

import sys


# 배열의 증가 부분 수열의 합 중 최대값을 찾는 함수
def getMaxSum(arr):
    max_sum = 0
    S = [0] * len(arr)  # S[i]: i번째 수를 포함하는 부분증가수열 합의 최댓값

    for i in range(len(arr)):
        # arr[max_j]는 arr[i]보다 작은 수 중 S[j]가 가장 큰 수  (i > j, arr[i] > arr[j])
        # S[i]는 arr[max_j]를 포함하는 부분증가수열에 현재 수 arr[i]를 합한 값
        max_j = i
        for j in range(i):
            if arr[i] > arr[j]:
                if S[max_j] < S[j]:
                    max_j = j
        S[i] = S[max_j] + arr[i]

        max_sum = max(max_sum, S[i])

    return max_sum


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))

    print(getMaxSum(A))