[DP] 백준 11055 파이썬 (가장 큰 증가 부분 수열) 실버2

-풀이

n = int(input())
seq = list(map(int, input().split()))
dp = [i for i in seq]

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

-풀이 설명(느낀점)

[30분 no sol] 비슷하게 풀고 dp 리스트 인덱스 값들도 다 같았는데 틀렸다. 구글링을 해보니 dp에 처음부터 seq값을 다 넣어주고 dp[i]값과 dp[j]+seq[i]값 중 최대값을 dp[i]에 초기화해주는 식으로 계산하여  가장 큰 증가 부분 수열을 구하였다.

내 풀이

n = int(input())
seq = list(map(int, input().split()))
dp = [0 for i in range(n)]

for i in range(n):
  for j in range(i):
    if seq[i] > seq[j]:
      dp[i] += seq[j]
for k in range(len(seq)):
  dp[k] += seq[k] 
print(max(dp))

 

dp[i]에 seq[i]보다 seq[j]가 작으면 그 값을 계속 합해주고 dp에 seq값을 마지막에 넣어줬는데, 답은 같았지만 예외 케이스가 있어서 틀린 것 같다.