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

출처::  www.acmicpc.net/problem/11055

분류:: dp

 

1. 문제 이해 및 해결과정

- 가장 긴 부분 수열 중에 부분수열의 합이 가장 큰 것을 구하라 는 문제 인줄 알았는데 - 그냥 길이에 관계없이 부분수열 중에 합이 가장 큰 것을 찾으면 된다. -dp[i] : i까지 수 중 가장 큰 부분수열의 합   ex) 1 100 2 50 60   3  5   6  7  8         1 101 3 53 113 6  11 17 24 32 1) dp배열은 최소 자기자신이므로 arr[i]로 초기화 2) 기준점 인덱스보다 작고, 자기자신보다 작은 값들 중에 가장 큰 값에 자기자신더해주기 => max(dp[i],dp[j]+arr[i])

 

2. 풀이방법

  1.dp

#가장 큰 증가 부분 수열
#https://www.acmicpc.net/problem/11055
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
dp=[0]*n
for i in range(n):
    dp[i]=a[i]
    for j in range(i):
        if a[j]<a[i]:
            dp[i]=max(dp[i],dp[j]+a[i])
print(max(dp))

  

3. 오답원인

 

4. 알게된 점