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

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.

1. DP정의

• dp: i번째까지 증가했을때 수열의 합의 최대값
• dp의 초기값은 입력받는 수열 A와 같도록 초기화 해준다

(예제)
5
10 90 20 80 100

(참고)
처음 d=a 라고 리스트를 복사하여 초기화를 했다가 오류가 발생했다.
파이썬의 리스트 변수는 리스트 객체를 직접 저장하고 있지 않다. 리스트 자체는 다른 곳에 저장되고 리스트의 참조값(리스트 객체의 위치)만 변수에 저장된다.
따라서 d=a 라고 하면 에 d리스트와 a리스트는 동일한 리스트 객체를 가리키게 된다.(얕은 복사)

그래서 위 코드와 같이, d 리스트의 값을 변경해주면 a 리스트이 값도 변경되어 결과값이 달라진다.
이를 해결할 수 있는 방법은 세가지가 있다.
1. 반복문을 이용한 복사: d = [i for i in a]
2. list()메소드 사용: d = list(a)
3. deepcopy() 메소드 사용:

	from copy import deepcopy
 	d = deepcopy(a)

2. 점화식 찾기

d[i] = max(d[j]+a[i], d[i])
j = i앞의 index중 a[i]보다 a[j]가 작을 경우

3. 코드

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

#dp정의 
d = [ i for i in a]

for i in range(1,n):
    for j in range(i):
        if a[j]<a[i]:
            d[i] = max(d[j]+a[i],d[i])

print(max(d))