백준: 11055 가장 큰 증가 부분 수열

문제

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

 

문제 풀이

 기존에 푼 문제 중 11053 가장 긴 증가하는 부분 수열의 풀이를 이해하고 있다면, 이 문제는 쉽게 풀 수 있다. 기존의 문제는 가장 긴 수열의 길이를 카운트 하였지만, 이 문제는 수열이 증가한다면 이전의 값들을 중첩시키면 문제의 답을 찾을 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))

    answer = [num for num in nums]

    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                answer[i] = max(answer[i], answer[j] + nums[i])
    print(max(answer))