Search

[백준 11055] 가장 큰 증가하는 부분 수열

[백준 11055] 가장 큰 증가하는 부분 수열

Tip

가장 긴 증가하는 부분 수열 문제와의 차이점과 기본적으로 유사
차이점은 DP 테이블 초기화시, 입력받은 수열을 그대로 가져와서 넣어주는 작업 필요.
1로 전부 초기화가 아닌, 수열의 각각의 인덱스 데이터는 기본적으로 더해진 값으로 초기화

풀이 소스 코드

import sys si = sys.stdin.readline # n과 수열 입력 n = int(si()) array = list(map(int, si().split())) # 증가하는 부분 수열의 합을 담을 DP 테이블 d = array[:] for i in range(1, n): for j in range(i): if array[i] > array[j]: d[i] = max(d[i], d[j] + array[i]) # 가장 큰 증가하는 부분 수열 길이 출력 print(max(d))
Python