[백준][DP][LIS] 11055. 가장 큰 증가하는 부분 수열

LIS (Longest Increasing Subsequence): 가장 큰 증가하는 부분 수열

 

11055. 가장 큰 증가하는 부분 수열

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

 

• 풀이
  • 이 문제는 LIS 중 가장 합이 큰 값을 구하는 문제 
  • i 전까지만 돌면서 현재값이 클때만 이전값에 현재위치 값 더해줌
    • 0번째 값은 for문에서 처리 못해주니까 따로 더해주기
  • 값이 같거나 작을 경우: 앞서 구해진 값이랑 그 위치값에서 다시 시작하는것중에 큰 걸로 

n=int(input())
num=list(map(int,input().split()))
dp=[1 for _ in range(n)]
dp[0]=num[0]
for i in range(n):
    for j in range(i):
        if num[i]>num[j]:
            dp[i]=max(dp[i], dp[j]+num[i])
        else:
            dp[i]=max(dp[i],num[i])

print(max(dp))