[백준/파이썬] 11055 가장 큰 증가 부분 수열

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

---

알고리즘 분류

• 다이나믹 프로그래밍

문제풀이

기본적인 구조는 가장 긴 부분 수열을 구하는 것과 비슷하다.

d[i]는 array[i]번까지의 증가 부분 수열의 합이다.

예를 들어, [2,1,2]과 같은 경우는 [2,1,3]이 나와야 한다.
2<1이 아니라면 else문에서 지금까지의 d값 혹은 자기 자신 값을 대입해준다.

소스코드

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

d=[1]*n
d[0]=array[0]
for i in range(1,n):
  for j in range(i):
    if array[j]<array[i]:
      d[i]=max(d[i], d[j]+array[i])
    else:
      d[i]=max(d[i], array[i])

print(max(d))