흰 스타렉스에서 내가 내리지

[BOJ] (DP) 11055번 가장 큰 증가하는 부분수열 본문

Problem Solving

[BOJ] (DP) 11055번 가장 큰 증가하는 부분수열

주씨. 2022. 3. 8. 16:27
728x90

i를 1씩 늘려가면서, 자신보다 왼쪽에 있으면서 작은 수들만 골라 다 더하고, 

만들어진 dp배열에서 가장 큰 값을 구하면 된다

 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().rstrip().split()))
dp = [a for a in arr]

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

 

 

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

 

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

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수

www.acmicpc.net